Search a 2D Matrix

1. The obvious way

   Scan every cell: O(rows x columns).

2. The key insight

   Pretend the matrix is one list of length rows x columns and binary search it. The value at position p is matrix[p // columns][p % columns]. No real flattening is needed.

3. The algorithm
   1. Treat the cells as positions 0 to rows x columns - 1.
   2. Take the middle position; turn it into (row, column) with divide and remainder.
   3. Read that cell and compare with the target, then discard half as in plain binary search.

Watch it run

positions 0 to 4 remain

def search_matrix(matrix, target):
    rows, columns = len(matrix), len(matrix[0])
    low, high = 0, rows * columns - 1
    while low <= high:
        middle = (low + high) // 2
        value = matrix[middle // columns][middle % columns]   # position -> (row, column)
        if value == target:
            return True
        if value < target:
            low = middle + 1
        else:
            high = middle - 1
    return False

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.