← Back to DSA Animator
Search a 2D Matrix LC #74 Medium Binary Search · Matrix
Problem

You are given an m × n integer matrix where each row is sorted in non-decreasing order and the first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in the matrix, or false otherwise. Must run in O(log(m × n)) time.

Example 1
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Explanation: Target 3 is at row 0, col 1 (virtual index 1).
Example 2
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Explanation: Target 13 is not present anywhere in the matrix.
Example 3
Input: matrix = [[1,1]], target = 0
Output: false
Constraints: 1 ≤ m, n ≤ 100  |  −10⁴ ≤ matrix[i][j], target ≤ 10⁴
Try Examples
Custom:
Approach
Treat m×n matrix as sorted 1D array of length m×n. Binary search on virtual index.
mid → row = mid/n, col = mid%n. Eliminate half per step. O(log(m×n)) time.
Matrix + Flattened View
Flattened virtual array  (index mid → matrix[mid/n][mid%n])
Variables
lo
—
hi
—
mid
—
val
—
target
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Flatten mentally: lo=0, hi=m*n-1
2
Loop while lo ≤ hi; compute mid=(lo+hi)/2
3
Map mid → matrix[mid/n][mid%n], get val
4
If val==target → return true
5
If val < target → lo=mid+1 (eliminate left half)
6
Else → hi=mid-1 (eliminate right half)
7
lo > hi: search exhausted → return false
Time
O(log(m·n))
Space
O(1)
Why This Works

Because each row is sorted and every row starts after the previous row ends, flattening the matrix gives a fully sorted 1D array. A virtual index mid maps bijectively to cell (mid/n, mid%n). Standard binary search then finds the target in O(log(m·n)) steps — equivalent to binary-searching an array of length m×n.