算法 | *二分查找 - 74. 搜索二维矩阵

难度：中等

题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
1. 每行中的整数从左到右按升序排列。
2. 每行的第一个整数大于前一行的最后一个整数。

示例 1:
输入:
matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

示例 2:
输入:
matrix = [
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

解题代码

解题思路一：先逐行查找，如果某一行的尾数小于等于 target，返回行坐标，然后对该行进行二分查找。注意空集单独处理。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix) == 1 and len(matrix[0]) == 0: # 矩阵为空集时
            return False
        index = -1 # 创建 Flag，考虑 target 遍历不到的情况
        for i in range(len(matrix)):
            if target <= matrix[i][-1]:
                index = i
                break # 按顺序查找，找到即终止遍历，赋值为 target 所在行
        if index == -1:
            return False
        # 按行进行二分查找
        left, right = 0, len(matrix[0]) - 1
        while left <= right:
            mid = (left + right)//2
            if matrix[index][mid] < target:
                left = mid + 1
            elif matrix[index][mid] > target:
                right = mid - 1
            else:
                return True
        return False

*解题思路二：这个题要是由二维变成一维就方便很多了，直接使用二分查找就行。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        
        # 二分查找
        left, right = 0, m * n - 1
        while left <= right:
                pivot_idx = (left + right) // 2
                pivot_element = matrix[pivot_idx // n][pivot_idx % n]
                if target == pivot_element:
                    return True
                else:
                    if target < pivot_element:
                        right = pivot_idx - 1
                    else:
                        left = pivot_idx + 1
        return False

答案参考：搜索二维矩阵
题目来源：力扣（LeetCode）