标签：right target idx 矩阵 mid 二维 74 left matrix

问题链接

https://leetcode.cn/problems/search-a-2d-matrix/description/

解题思路

我们可以确定，数据是有序的。所以我们有2种办法用二分来解决。

第一种，我们可以写个下标映射函数，把矩阵当做一维数组来进行遍历。

第二种，我们可以先对列进行二分，得到数据存在于哪个行。

然后对这个行进行二分，得到数据存在与否。

此时我们选择第二种方式。

代码

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        left, right = 0, len(matrix)-1
        target_idx = -1
        while left <= right:
            mid = (left+right)>>1
            if matrix[mid][0]<=target<=matrix[mid][-1]:
                target_idx = mid
                break
            elif matrix[mid][0]>target:
                right = mid - 1
            else:
                left = mid + 1
        if target_idx == -1:
            return False
        left, right = 0, len(matrix[target_idx])-1
        while left <= right:
            mid = (left+right)>>1
            if matrix[target_idx][mid] == target:
                return True
            elif matrix[target_idx][mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

 

标签：right,target,idx,矩阵,mid,二维,74,left,matrix
From： https://www.cnblogs.com/bjfu-vth/p/17045267.html