Search a 2D Matrix

Binary search a matrix whose rows continue each other in sorted order, by treating it as one flat sorted array and mapping each index back to a row and column.

The idea

Each row is sorted and starts above where the previous row ended, so reading the matrix row by row gives one sorted list of m · n numbers. Binary search that list by index without building it: index i lives at row i / n, column i % n.

Code

public static bool SearchMatrix(int[][] matrix, int target) {
    int m = matrix.Length, n = matrix[0].Length;
    int lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int v = matrix[mid / n][mid % n];
        if (v == target) return true;
        if (v < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

Tips

• Divide and take the remainder by n, the number of columns, not by m.
• A different problem, Search a 2D Matrix II, only sorts rows and columns separately; there you start at the top-right corner and step left or down in O(m + n).
• Two binary searches (first pick the row, then search inside it) also give O(log m + log n), which is the same bound.

In the .NET library

int[][] is a jagged array (an array of row arrays), so matrix[r][c] is two lookups. A rectangular int[,] would be matrix[r, c] with GetLength(0) and GetLength(1).