正文
leetcode 【Search a 2D Matrix 】python 实现
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目 ：
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target =
3
, return
true
.
代码 ：oj测试通过 Runtime: 75 ms
class Solution:
# @param matrix, a list of lists of integers
# @param target, an integer
# @return a boolean
def searchInline(self, line, target):
start = 0
end = len(line)-1
while start <= end :
if start == end :
return [False,True][line[start]==target]
if start+1 == end :
if line[start]==target or line[end]==target :
return True
else:
return False
mid=(start+end)/2
if line[mid]==target :
return True
elif line[mid]>target :
end = mid-1
else :
start = mid+1 def searchMatrix(self, matrix, target):
if len(matrix) == 0 :
return False if len(matrix) == 1 :
return self.searchInline(matrix[0], target) if len(matrix) == 2 :
return self.searchInline([matrix[1],matrix[0]][matrix[1][0]>target], target)\ start = 0
end = len(matrix)-1
while start <= end :
if start == end:
return self.searchInline(matrix[start],target)
if start+1 == end:
if matrix[start][0] <= target and matrix[end][0] > target:
return self.searchInline(matrix[start],target)
if matrix[end][0] < target :
return self.searchInline(matrix[end],target)
mid = (start+end+1)/2
if matrix[mid][0] <= target and matrix[mid+1][0] > target:
return self.searchInline(matrix[mid],target)
elif matrix[mid][0] > target :
end = mid-1
else :
start = mid+1
思路 ：
先按行二分查找，再按列二分查找。
代码写的比较繁琐。
