Search a 2D Matrix — Binary Search in One Pass

The Problem

You are given an m x n matrix with two properties: each row is sorted left to right, and the first element of each row is greater than the last element of the previous row. Find whether a target value exists.

The two properties together mean the matrix is, conceptually, one long sorted array reshaped into m rows of n columns. That’s the key insight that unlocks the O(log(mn)) solution.

Intuition

Because every row begins with a value larger than the previous row’s last value, the matrix flattened in row-major order is itself a sorted 1D array. So a standard binary search over indices 0 .. m*n - 1 works; the only adjustment is converting each flat index k back to a (row, col) pair via row = k // n, col = k % n before reading.

A weaker matrix that is only sorted within each row and each column (no inter-row guarantee) would need a different approach — the top-right or bottom-left “staircase walk” — but here we have the stronger ordering.

Explanation with Example

Take the matrix [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]] with target = 11.

flat:  0  1  2  3  4  5  6  7  8  9  10 11
val:   1  3  5  7 10 11 16 20 23 30 34 60

iter 1: lo=0 hi=11 mid=5 val=11 -> match, return True

mapping: mid=5 -> row=5//4=1, col=5%4=1 -> matrix[1][1]=11

If the target were 13, the search would shrink to lo=5, hi=5 (mid=5 val=11 < 13 -> lo=6), then lo=6 hi=5 fails, return False.

Code

Standard textbook binary search with one twist: the comparison uses matrix[mid // n][mid % n] instead of arr[mid].

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

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        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 val = matrix[mid / n][mid % n];
            if (val == target) return true;
            if (val < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
}

#include <vector>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size(), n = matrix[0].size();
        int lo = 0, hi = m * n - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int val = matrix[mid / n][mid % n];
            if (val == target) return true;
            if (val < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return false;
    }
};

Edge Cases

An empty matrix or a matrix with empty rows returns False. A 1x1 matrix is handled by the standard binary-search bounds. A target smaller than the minimum or larger than the maximum exits without a match.

Integer overflow on lo + hi is fine in Python but worth mentioning for Java or C++; use lo + (hi - lo) / 2 there.

Complexity Analysis

Time is O(log(mn)) because the search halves the flat range each iteration. That’s strictly better than the O(m + n) staircase approach when both dimensions are large.

Space is O(1): three integer variables. No recursion, no allocation.

How to Explain It in an Interview

Open with the structural observation: “Each row’s first value is greater than the previous row’s last value, so the entire matrix is sorted in row-major order. I can treat it as a flat sorted array of length m*n and binary search.” Then write the binary search, narrating the mid // n and mid % n conversion.

The interviewer’s likely follow-up is the row-and-column variant (no total order). Mention that the flat trick doesn’t work there; you need the top-right or bottom-left walk that achieves O(m + n).

Related Problems

• Search a 2D Matrix II — only rows and columns sorted, staircase walk.
• Search in Rotated Sorted Array — binary search with a twist.
• Search Insert Position — classic binary search.
• Kth Smallest Element in a Sorted Matrix — binary search on value.