Course contentsShow
← Computer Science
Lesson 819 of 2,87219. Searching and SelectionFree lesson

Binary Search in 2D Matrices

Apply binary search principles to search sorted 2D matrices with row and column ordering properties.

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:

  1. Treat as a flattened array (fully sorted matrices): If element [i][j] maps to index i * cols + j, you can perform standard binary search on this "virtual" 1D array, converting indices back to 2D coordinates.

  2. 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.