Search a 2D Matrix

The machine must find a target in an m×n matrix where each row is sorted and every row's last element is smaller than the next row's first — the whole matrix is one flattened sorted array. The insight: index arithmetic maps a flat index to a cell: row = mid // n, col = mid % n. Run ordinary binary search over 0..m*n-1 and translate at every step.

def search_matrix(matrix, target):
    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]
        if val == target:
            return True
        if val < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Steps: (1) treat the matrix as an array of length m*n, (2) binary search, converting each midpoint with divmod, (3) return on the first exact match.

Time is O(log(m*n)) — one search over the flattened space. Space is O(1).

Trickiest edge cases: a single row or single column — the divmod math still holds because n comes from the real matrix. Watch the division direction: mid // n uses the number of columns, not rows. The row-major layout is what the problem guarantees; if only per-row sorting were guaranteed, this approach would break.