Search a 2D Matrix

mediumBinary Search20 stepsJava · Python · C++

Each row is sorted and starts after the previous row ends, so the whole matrix is one sorted list read row by row. Binary search over indices 0..m·n−1 and convert each index to (i / n, i % n).

▶ Watch the animated trace

Traced input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 16 → true. Original problem: neetcode.io/problems/search-2d-matrix

Complexity

BestO(1)

AverageO(log(m·n))

WorstO(log(m·n))

SpaceO(1)

One binary search over all cells.

Key idea

Treat the matrix as a sorted 1D array of length m·n.
Index k maps to row k / n, column k % n.
Then it's plain binary search.

Common mistakes

Two separate binary searches (row, then column) also work but are easier to get wrong.
Using m instead of n (the number of columns) in the index conversion.

Solution

Java

boolean 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 val = matrix[mid / n][mid % n];
        if (val == target) {
            return true;
        }
        if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

Python

def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    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

C++

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    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

Each one has its own trace in the interactive view.

Case	Input	Answer
Missing value 13 would sit between 11 and 16.	`matrix = [[1, 3, 5, 7], [10, 11, 16, 20]], target = 13`	`false`
Single cell One comparison.	`matrix = [[5]], target = 5`	`true`
Single row Works like a normal array.	`matrix = [[1, 3]], target = 3`	`true`
Single column n = 1, so each index is its own row.	`matrix = [[1], [3], [5]], target = 4`	`false`