题目
Write an efficient algorithm that searches for a value target
in an m x n
integer matrix 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.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Example 2:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
思路
两次二分查找,第一次查找目标值在数组的哪一列,第二次查找目标值在数组的哪一行。
代码
python版本:
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
l, r = 0, len(matrix)
while l < r:
mid = (l+r)//2
if matrix[mid][0] > target:
r = mid
elif matrix[mid][-1] >= target:
l = mid
break
else:
l = mid+1
x = l
if x < 0 or x >= len(matrix):
return False
l, r = 0, len(matrix[x])
while l < r:
mid = (l+r)//2
if matrix[x][mid] > target:
r = mid
elif matrix[x][mid] < target:
l = mid+1
else:
return True
return False