Coding interview problems › Binary Search

🔍 Binary Search Medium

Search a 2D Matrix

Search a 2D Matrix explained: treat a row-sorted matrix as one flattened sorted array and binary search it in O(log(m·n)). Tested Python and a live visual.

Also searched as: binary search in a 2D matrix · search in row-wise and column-wise sorted matrix · matrix as a flattened sorted array

🔍

Try it live Free

Binary Search

The binary search lab shows the halving loop on a 1D sorted array; this problem is exactly that loop, with the index translated to a row and column before each look.

Open the playground →

The problem

You are given an m x n matrix where each row is sorted left to right and the first value of every row is larger than the last value of the row above. Decide whether target appears in the matrix, in O(log(m·n)) time.

Inputmatrix = [[1, 4, 6], [9, 11, 15], [20, 22, 30]], target = 11
OutputTrue
Inputsame matrix, target = 10
OutputFalse

The key insight

Read row by row, the matrix is one long sorted list of m·n values. You do not need to build that list: index i of the imaginary list lives at row i // n, column i % n. Run ordinary binary search over 0 .. m·n - 1 using that mapping.

Brute force first: Checking every cell is O(m·n); binary searching each row separately is O(m log n), better but still not the best.

Step-by-step approach

  1. Handle an empty matrix (or empty rows) by returning False.
  2. Let m and n be the number of rows and columns; search indices lo = 0 to hi = m·n - 1.
  3. For each mid, read the value at matrix[mid // n][mid % n].
  4. Compare with the target and move lo or hi exactly as in normal binary search.
  5. Return True on a match, False when the range is empty.

Python solution

PYTHON 3tested
def search_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    m, n = len(matrix), len(matrix[0])
    lo, hi = 0, m * n - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        val = matrix[mid // n][mid % n]     # flattened index -> (row, col)
        if val == target:
            return True
        if val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Complexity

TimeO(log(m·n))
SpaceO(1)

It is a single binary search over m·n positions, and the index-to-cell mapping is constant time.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(log(m·n)) time, which equals O(log m + log n), and O(1) extra space.

What if rows and columns are sorted but rows do not continue from each other?

Then the matrix is not one sorted list. Start at the top-right corner: move left if the value is too big and down if it is too small. That takes O(m + n).

Is two binary searches (first the row, then the column) also fine?

Yes. Binary search the first column to find the only row that could hold the target, then binary search inside that row. The total is the same O(log m + log n).

Why does the index mapping work?

Rows are laid out one after another, each of length n, so the i-th value in reading order is in row i // n, at offset i % n within that row.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Binary Search Binary Search lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.