python实现leetcode之74. 搜索二维矩阵

解题思路

一般的二分查找
假设第一行的结尾连接第二行的开头，这就是一个有序的一维数组
mid = start + (end-start)//2 就是中点，将中点转为二维数组中的行列号
然后通过比较判断是在前半部分还是在后半部分

74. 搜索二维矩阵

代码

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix: return False
        return bin_search(matrix, target, 0, len(matrix) * len(matrix[0])-1)


def bin_search(matrix, target, start, end):
    if start > end: return False
    mid = start + (end-start)//2
    i, j = divmod(mid, len(matrix[0]))
    if matrix[i][j] == target:
        return True
    elif matrix[i][j] > target:
        return bin_search(matrix, target, start, mid-1)
    else:
        return bin_search(matrix, target, mid+1, end)