Binary Search in 2D Matrices
What you'll learn: How to efficiently search sorted 2D matrices by leveraging their ordering properties with binary search.
A 2D matrix with special ordering properties can be searched much faster than scanning every element. When rows are sorted left-to-right and columns are sorted top-to-bottom, we can use binary search principles to eliminate large portions of the matrix with each comparison.
The Core Idea
Imagine a phone book where each page's entries are alphabetically sorted, and the first entry of each page is also in alphabetical order. If you're looking for "Smith," you wouldn't read every entry—you'd skip entire pages based on comparisons.
For matrices with row-wise and column-wise sorting, two common approaches exist:
-
Treat as a flattened array (fully sorted matrices): If element
[i][j]maps to indexi * cols + j, you can perform standard binary search on this "virtual" 1D array, converting indices back to 2D coordinates. -
Search from a corner (row-sorted, column-sorted): Start at the top-right or bottom-left corner. At each step, compare the target with the current element:
- If the target is smaller, move left (eliminate the current column)
- If the target is larger, move down (eliminate the current row)
- This eliminates one row or column per step, achieving O(rows + cols) time
Example Walkthrough
Given a matrix where rows increase left-to-right and columns increase top-to-bottom, searching for 15 starting from the top-right:
- Compare with
20→ target smaller → move left - Compare with
15→ found!
Each comparison rules out an entire row or column.
Key Takeaway:
Binary search extends to 2D matrices by exploiting their ordering: either treat a fully sorted matrix as a 1D array for O(log(rows × cols)) search, or use corner-based elimination for O(rows + cols) search in row-and-column-sorted matrices.