To determine whether a given number exists in a sorted 2D matrix, we use a binary search approach, but with a twist: we treat the 2D matrix as a 1D sorted array.
Understanding the Matrix Structure
The matrix has two important properties:
- Each row is sorted in increasing order.
- The first number of a row is greater than the last number of the previous row. This means the entire matrix is sorted when viewed as one long list.
How We Search
We imagine flattening the matrix into a 1D array (without actually doing it in code). If the matrix has m
rows and n
columns, then:
- The virtual 1D index
mid
can be mapped to 2D as matrix[row][col]
, where:
row = Math.floor(mid / n)
col = mid % n
Different Possibilities to Consider
- If the matrix is empty (e.g.,
[]
), we simply return false
. There is no data to search.
- If the matrix has rows but no columns (e.g.,
[[]]
), we also return false
.
- If the target is smaller than the first element, it cannot exist in the matrix.
- If the target is greater than the last element, it also cannot exist.
- For all other values, we run binary search from
start = 0
to end = m * n - 1
.
At each step, we check if the mid element matches the target:
- If yes → return
true
- If target is smaller → search left half
- If target is greater → search right half
This approach ensures we don’t have to scan every row or column manually. It works in O(log(m × n)) time, which is highly efficient for large matrices.
By converting between 1D and 2D indices using basic math, we can search across rows and columns in a clean and fast way.