编写一个高效的算法来判断 m x n
矩阵中,是否存在一个目标值。该矩阵具有如下特性:
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
示例 1:
输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true
# [74] 搜索二维矩阵
#
# @lc code=start
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
def twoserch(nums,i,j,target):
# i=0
# j=len(nums)-1
if nums[0]==target:
return True
mid=(i+j)//2
while i<j-1:
mid=(i+j)//2
if nums[mid]==target:
return True
elif nums[mid]<target:
i=mid
else:
j=mid
return False
j=-1
for i in range(len(matrix)):
if target<matrix[i][-1]:
j=i
break
elif target==matrix[i][-1]:
return True
if j == -1:
return False
else:
lens=len(matrix[j])
return twoserch(matrix[j],0,lens-1,target)
# @lc code=end