Search a 2D Matrix as One Flattened Sorted Array

"Search a 2D Matrix" shows up again and again in Amazon, Microsoft, Meta phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Modified Binary Search pattern quickly and code it cleanly. Part 10 of 11 in the Modified Binary Search arc.

The Problem

An m x n matrix has rows sorted left to right, and each row's first element greater than the previous row's last — i.e., row-major order is globally sorted. Given a target, return whether it exists, in O(log(m·n)). The test is whether you see one array wearing a matrix costume.

Input:  matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3
Output: True

Recognizing the Modified Binary Search Pattern

Binary search is not about sorted arrays — it is about any monotonic predicate: if the answer space splits into a false-region followed by a true-region, you can halve it. FAANG interviews rarely ask the textbook version; they ask rotated arrays, boundary-finding, and search-on-the-answer problems where the array being searched is conceptual. Getting the loop invariant right is the whole game.

The row-boundary condition makes the whole matrix one sorted sequence of length m·n. One binary search over virtual indices, with divmod(idx, n) translating to row and column, preserves the pure O(log(m·n)) bound — no two-phase search needed.

The Approach

Binary search over [0, m·n). For each mid, r, c = divmod(mid, n) reads the element without materializing anything. Standard compare-and-halve from there.

Contrast with the sibling problem (Matrix II: rows and columns sorted, but not globally) where this mapping is invalid and the staircase walk from a corner is the answer. Confusing the two is the classic error — name both up front and pick correctly.

Python Solution

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    """True if target exists in a row-major globally sorted matrix."""
    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
        r, c = divmod(mid, n)
        value = matrix[r][c]
        if value == target:
            return True
        if value < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Complexity

• Time: O(log(m·n)) — one binary search over the virtual flattened array
• Space: O(1) — divmod mapping, no copies

Interview Tips and Follow-Ups

• Ask which matrix variant you have before coding — globally sorted (this) vs row-and-column sorted (staircase walk) is a deliberate ambiguity trap.
• Two-phase (binary search the right row, then within it) is also O(log m + log n) — equivalent complexity; the flattened version is just less code.
• divmod again — the same index-mapping idiom appears in heap array math and matrix problems; small toolkit, big coverage.

That wraps part 10 of the Modified Binary Search arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.