转载请注明出处: http://www.cnblogs.com/gufeiyang
个人微博：flysea_gu
题目描述：
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
For example,
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.
思路： 单调的矩阵-->二分筛选
<1> 砍上 二分右列 从上到下找到第一个比target大的
<2> 砍下 二分左列 从下到上找到第一个比target小的
<3> 砍左 二分下行 从左到右找到第一个比target大的
<4> 砍右 二分上行 从右到左找到第一个比target小的
具体代码：
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
n = len(matrix)
if n==0:
return False
m = len(matrix[0])
if m==0:
return False
lr = 0
lc = 0
rr = n-1
rc = m-1
while lr<=rr and lc<=rc:
l = lr
r = rr
while l<=r:
k = (l+r)/2
if matrix[k][rc] == target:
return True
elif matrix[k][rc] < target:
l = k+1
else: r = k-1
if l >= n:
return False
lr = l
l = lr
r = rr
while l<=r:
k = (l+r)/2
if matrix[k][lc] == target:
return True
elif matrix[k][lc] < target:
l = k+1
else: r = k-1
if r <0 :
return False
rr = r
l = lc
r = rc
while l<=r:
k = (l+r)/2
if matrix[rr][k] == target:
return True
elif matrix[rr][k] < target:
l = k+1
else : r = k-1
if l>=m:
return False
lc = l
l = lc
r = rc
while l<=r:
k = (l+r)/2
if matrix[lr][k] == target:
return True
elif matrix[lr][k] < target:
l = k+1
else : r = k-1
if r<0:
return False
rc = r
return False
LeetCode 240. Search a 2D Matrix II
原文：http://www.cnblogs.com/gufeiyang/p/5203393.html