How does binary search apply to Search a 2D Matrix?

Binary search treats the 2D matrix as a virtual flattened array, allowing logarithmic search by mapping indices to rows and columns instead of scanning linearly.

What happens if the target is the first or last element?

The algorithm correctly identifies targets at matrix boundaries by computing the mid-point mapping and avoids off-by-one errors during index translation.

Can this approach handle non-rectangular matrices?

The standard solution assumes all rows have equal columns; non-rectangular matrices require additional checks or adjusted index mapping to preserve correctness.

Why is linear row search incorrect here?

Linear row scanning violates the O(log(m * n)) requirement and misses the optimization gained from binary search over the fully flattened matrix index space.

What is the key failure mode in this problem?

A common failure mode is miscalculating row and column from the 1D index, which causes false negatives or incorrect comparisons during binary search iterations.

#74

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。示例 1：输入： matrix = [[1,3,5,…

数组二分查找矩阵

题目描述

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

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。

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

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

lightbulb

解题思路

方法一：二分查找

我们将二维矩阵逻辑展开，然后二分查找即可。

时间复杂度 $O(\log (m \times n))$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

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) >> 1
            x, y = divmod(mid, n)
            if matrix[x][y] >= target:
                right = mid
            else:
                left = mid + 1
        return matrix[left // n][left % n] == target

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how to map a 1D index back to 2D coordinates in the matrix?
question_mark
Can you adjust your binary search if the target is smaller than the first element or larger than the last?
question_mark
Will you maintain O(log(m * n)) complexity without scanning any row linearly?

warning

常见陷阱

外企场景

error
Miscomputing row and column from a 1D index leading to wrong value comparisons.
error
Attempting linear search in individual rows which breaks the logarithmic time requirement.
error
Incorrect handling of edge targets that match the first or last element of the matrix, causing off-by-one errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Search a 2D matrix II where rows and columns are independently sorted but not fully flattened.
arrow_right_alt
Search a rotated 2D matrix with unknown rotation point while preserving sorted property in rows.
arrow_right_alt
Find the k-th smallest element in a sorted 2D matrix using a similar binary search over value space.

help

常见问题

外企场景

继续练习

#240 搜索二维矩阵 II #363 矩形区域不超过 K 的最大数值和 #378 有序矩阵中第 K 小的元素