搜索二维矩阵II

Leetcode Link: 240. 搜索二维矩阵 II - 力扣（LeetCode） 剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode）

题目

编写一个高效的算法来搜索 [m，n] 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

解法一

思路： 之前有一个题目好像是这样的，不知道咋描述的，但是对于输入的矩阵，满足的是任意一个位置的左上位置的都比他小，其他位置的都比他大。那个好像可以更快的二分，同时捏着右上角提起来变成了二叉搜索树。

但是这个不行，譬如例 1 中的 5 位置，就不满足要求

因此本题思路略有不同，但是依然从右上角入手，

1. 当前位置比目标大，左移
2. 当前位置比目标小，下移

题解：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row = 0
        col = len(matrix[0])-1
 
        m = len(matrix)  # 行数
        n = len(matrix[0])
 
        while(row<m and col>=0):
            if matrix[row][col] > target:
                col -= 1
            elif matrix[row][col] < target:
                row += 1
            else:
                return True
        
        return False

解法二

思路：二分查找

使用二分查找的时候，就不从右上角开始了，这里直接放贴

由于矩阵 $\text{matrix}$中每一行的元素都是升序排列的，因此我们可以对每一行都使用一次二分查找，判断target 是否在该行中，从而判断 $\text{target}$ 是否出现。

注意：行与行之间的数字可能会有重复的！因此必须每行都要找，不能头尾一比较就出结论。

题解：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            idx = bisect.bisect_left(row, target)
            if idx < len(row) and row[idx] == target:
                return True
        return False

启发和联系