74. 搜索二维矩阵

题目链接：74. 搜索二维矩阵

题目描述

给你一个满足下述条件的 m x n 整数矩阵：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

核心思考：降维法开展全局二分检索

由于矩阵符合双重条件：这一行左到右上升、并且上一行尾巴的下一级阶梯接力也比它大。
我们可以极其直接地在脑海里将其“首尾连缀捆绑”，直接将它铺平构想成了一个完美的升序连续一维数组 (1D Array)！

此时这个问题极度简单了，把总搜索目标总数量上限设定为 m * n。原本对于暴力搜需要消耗 O(M*N) 的巡查，在这个连续空间用常规的 二分查找 便可以暴压到极限的对数耗时。

唯一的阻碍：假借中点打通映射
普通一维区间得到搜寻中点下标后是 nums[mid]，在这个虚拟对标的方案里，我们要把下标重新反射投射回原本的二维抽屉。其实非常质朴：
假设一行能容纳多少人是 n 的列量。

• 我在哪一行：mid // n （总排序席位除以排宽）
• 我在哪一列：mid % n （总定位所剩余在宽度的偏移量）
  通过定位器 matrix[mid // n][mid % n] 我们就完美获得了比较元！剩下的只有一维常规模板收缩。

解题思路 (Python)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1 
        
        while left <= right:
            mid = (left + right) // 2
            
            # 使用技巧执行降维坐标回打还原
            x = matrix[mid // n][mid % n]
            
            if x == target:
                return True
            if x < target:
                left = mid + 1
            else:
                right = mid - 1
                
        return False

复杂度分析

• 时间复杂度：O(log(M * N))，整体算法对总有效网格元素总量进行了一次极其紧凑连贯全局的二分处理探测，所费开支是微乎其微的对数级别。
• 空间复杂度：O(1)，单纯设立游标常量参数寄存位置进行坐标轴重构与搜寻。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

m n
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
...
am1 am2 am3 ... amn

第一行输入矩阵的行数 m 和列数 n，随后输入 m 行 n 列的矩阵元素。

完整代码：

import sys

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    m, n = len(matrix), len(matrix[0])
            left, right = 0, m * n - 1

            while left <= right:
                mid = (left + right) // 2

                # 使用技巧执行降维坐标回打还原
                x = matrix[mid // n][mid % n]

                if x == target:
                    return True
                if x < target:
                    left = mid + 1
                else:
                    right = mid - 1

            return False

def main():
    data = sys.stdin.read().strip().split()
    m, n = int(data[0]), int(data[1])
    idx = 2
    matrix = []
    for i in range(m):
        row = list(map(int, data[idx:idx+n]))
        matrix.append(row)
        idx += n

    sol = Solution()
    result = sol.searchMatrix(matrix)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

echo -e "3 3\n1 2 3\n4 5 6\n7 8 9" | python solution.py