Understanding the Problem
We are given a 2D matrix and a target number. The matrix has two special properties:
- Each row is sorted in increasing order from left to right.
- The first number of each row is greater than the last number of the previous row.
This means if we "flatten" the matrix, the elements form a fully sorted 1D array. Our task is to determine whether the target number exists in the matrix. A beginner might think of scanning every row and column, but that would be inefficient. Instead, we will use a binary search approach that treats the entire 2D matrix as a sorted 1D list — without actually flattening it.
Step-by-Step Solution with Example
step 1: Represent the matrix and target
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 60]
]
target = 3
We want to check whether the number 3 exists in this matrix.
step 2: Understand the matrix as a virtual 1D array
The matrix has m = 3
rows and n = 4
columns. So the total number of elements is m × n = 12
.
Imagine indexing this matrix from 0 to 11, like a normal 1D array. The key idea is:
row = Math.floor(index / n)
col = index % n
This lets us map any 1D index to a 2D coordinate in the matrix.
step 3: Initialize binary search
We set start = 0
and end = m × n - 1 = 11
.
We will now perform binary search between these indices.
step 4: Perform the binary search loop
Repeat the following until start > end
:
- Find the middle index:
mid = Math.floor((start + end) / 2)
- Map this index to 2D:
row = Math.floor(mid / n)
, col = mid % n
- Check
matrix[row][col]
against the target:
- If it matches → return
true
- If it’s less than the target → move to right half:
start = mid + 1
- If it’s more than the target → move to left half:
end = mid - 1
For our example, 3 is found at index 1 (which maps to row 0, column 1).
step 5: Return the result
If the binary search completes without finding the target, return false
.
Edge Cases
- Empty matrix: If the matrix is
[]
, return false
. No data to search.
- Matrix with empty rows: For example,
[[]]
→ no columns → return false
.
- Target smaller than the smallest element: return
false
.
- Target greater than the largest element: return
false
.
- These checks help us avoid unnecessary work and prevent runtime errors.
Finally
This approach is efficient and elegant. By treating the 2D matrix as a virtual 1D sorted array, we leverage binary search for O(log(m × n)) time complexity. This is especially helpful for large matrices.
For beginners, it's important to understand how index mapping works and how binary search helps us reduce the search space efficiently. Always check for edge cases first, then implement the main logic clearly and step by step.
Comments
Loading comments...