74. 搜索二维矩阵

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)-1
        n = len(matrix[0])-1
        left = 0
        right = m
        while left<=right:
            mid = (left+right)>>1
            if matrix[mid][0]==target or matrix[mid][n]==target:
                return True
            elif matrix[mid][0] < target and target < matrix[mid][n]:
                # 继续二分
                L = 0
                R = n
                while L<=R:
                    inner_mid = (L+R)>>1
                    if matrix[mid][inner_mid]==target:
                        return True
                    elif target < matrix[mid][inner_mid]:
                        R = inner_mid-1
                    elif matrix[mid][inner_mid] < target:
                        L = inner_mid+1
                return False
            elif target < matrix[mid][0]:
                right = mid-1
            else:
                left = mid+1
        return False