搜索二维矩阵(二分法)

搜索二维矩阵

1、题目

图1

2、题解

两次二分查找

先二分查找找到小于target的是哪一行，并且下一行的第一个数大于target，然后在该行二分查找到target。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        r_t,r_b = 0,len(matrix)
        l_l,l_r = 0,len(matrix[0])
        m,n = len(matrix), len(matrix[0])
        col0 = [col[0] for col in matrix]
        while r_t<r_b:
            r_mid = r_t + (r_b - r_t)//2
            if col0[r_mid]<= target:
                r_t = r_mid+1
            else:
                r_b = r_mid
        if r_t  < 0 :
            return False

        while l_l<l_r:
            l_mid = l_l + (l_r - l_l)//2
            if matrix[r_t-1][l_mid]<target:
                l_l = l_mid + 1
            else:
                l_r = l_mid

        if l_l >= n:
            return False
            
        if matrix[r_t-1][l_l] == target: 
            return True
        
        return False