Problem Statement

Search a 2D Matrix

You are given an m x n grid of numbers (m rows and n columns). Two rules make this grid special. First, every row is sorted from small on the left to large on the right. Second, the first number of each row is bigger than the last number of the row above it. So if you read the grid like a book, left to right and top to bottom, the numbers only ever go up. Given a target number, return true if it is somewhere in the grid, or false if it is not.

mediumBinary SearchBinary SearchTime: O(log(m*n)) · Space: O(1)

Signals to notice

sorted rows and columnssearch in 2D matrixtreat as 1D sorted array

Brute force first

Linear scan of all m × n elements. Ignores the sorted structure completely. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Treat the 2D matrix as a flattened 1D sorted array. Binary search with index mapping: row = mid / cols, col = mid % cols. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=13`

init: m=3, n=4, left=0, right=11 (treat as 1D array of length 12)
mid=5 -> [5//4][5%4]=[1][1]=11; 11<13 -> left=6
mid=8 -> [8//4][8%4]=[2][0]=23; 23>13 -> right=7
mid=6 -> [6//4][6%4]=[1][2]=16; 16>13 -> right=5
left=6 > right=5 -> loop exits
return false (13 not in matrix)

What must stay true

Because the first element of each row is greater than the last element of the previous row, the matrix IS a sorted array when read left-to-right, top-to-bottom. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

left, right = 0, m*n - 1
while left <= right:
    mid = (left + right) // 2
    val = matrix[mid // n][mid % n]   # map flat index -> 2D
    if val == target: return true
    elif val < target: left = mid + 1
    else: right = mid - 1
return false

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Doing two binary searches (find row, then find column) — works but is unnecessary. A single binary search on the flattened index is simpler and just as fast. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Binary Search Pattern