Matrix Binary Search

Description

Matrix binary search finds a value in a sorted grid without checking every cell. Which method works depends on how the grid is sorted. If it reads as one sorted sequence, row after row, binary search it like a flat array and convert each index to a row and a column. If each row and each column is only sorted on its own, walk a staircase from a corner, ruling out a whole row or column at every step.

We'll go from simple to more technical:

1. The pattern: binary search over a flat index.
2. A second flavor: staircase search from the top-right corner.
3. Where virtual indexes and two-way-sorted structures show up in production.
4. Matching the method to the guarantee the matrix actually gives.

The approach

Checking every cell takes O(rows x cols). But suppose each row starts where the row above ended, so the whole grid reads as one sorted list. Then number the cells 0, 1, 2, and so on, row by row, and binary search those numbers. Cell number i is at row i / cols and column i % cols. You never build the flat list; you only convert numbers.

Searching for 20 in a grid with 4 columns:

int lo = 0, hi = rows * cols - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    int value = matrix[mid / cols][mid % cols];   // flat index -> (row, col)
    if (value == target) return true;
    if (value < target) lo = mid + 1;
    else hi = mid - 1;
}
return false;

def search(matrix: list[list[int]], target: int) -> bool:
    rows, cols = len(matrix), len(matrix[0])
    lo, hi = 0, rows * cols - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        value = matrix[mid // cols][mid % cols]   # flat index -> (row, col)
        if value == target:
            return True
        if value < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

A second flavor: staircase search from a corner

A weaker guarantee is more common. Each row is sorted left to right and each column top to bottom. But a row may start with a smaller value than the row above ended with. Flat binary search fails here, because the grid no longer reads as one sorted list. Start at the top-right corner instead. Moving left makes values smaller, and moving down makes them bigger. So one comparison tells you which way to go, and each step rules out a whole row or column.

Searching for 11 in this grid, where row 0 ends at 14 but row 1 starts at 5:

The walk visits 14 (too big: go left), 10 (too small: go down), 12 (too big: left), 9 (too small: down), then finds 11.

int row = 0, col = cols - 1;   // top-right corner
while (row < rows && col >= 0) {
    int value = matrix[row][col];
    if (value == target) return true;
    if (value > target) col--;   // eliminate this whole column
    else row++;                  // eliminate this whole row
}
return false;

def search(matrix: list[list[int]], target: int) -> bool:
    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1            # top-right corner
    while row < rows and col >= 0:
        value = matrix[row][col]
        if value == target:
            return True
        if value > target:
            col -= 1                  # eliminate this whole column
        else:
            row += 1                  # eliminate this whole row
    return False

The corner matters. From the top-left, moving down and moving right both make values bigger. No comparison can tell you which way is safe, so the walk doesn't work from there.

Where you'll see it

A sorted sequence is often stored in pieces: pages of results, or fixed-size blocks on disk. You can still binary search it by turning a position in the sequence into "which block, and where in it", the same conversion as row and column. That avoids building a merged copy first.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Each row and each column is sorted, but row 2's first value is smaller than row 1's last. Can you use flat binary search?

2. Why does the staircase start at the top-right corner rather than the top-left?

3. A grid has 2 rows and 3 columns. Which cell is flat index 4?

Key takeaways

• A grid that reads as one sorted list can be binary searched through a flat index: row i / cols, column i % cols. That's O(log(rows x cols)).
• A grid sorted only by row and by column needs the staircase walk, O(rows + cols).
• Start the staircase at the top-right or bottom-left, where the two moves change the value in opposite directions.
• Check which sort guarantee the grid really has before choosing a method.