Problem statement

You are given an m x n matrix where each row is sorted in non-decreasing order and the first integer of each row is greater than the last integer of the previous row. Given a target, return true if it is in the matrix.

Your solution must run in O(log(m*n)) time.

Example 1

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints

• 1 <= m, n <= 8
• -500 <= values, target <= 500

Hints for Search a 2D Matrix

1. Hint 1

   The whole matrix reads as one sorted list of length m*n.

2. Hint 2

   Binary search index k, mapping it to matrix[k / n][k % n].

How to solve Search a 2D Matrix

The two guarantees together — each row sorted, and every row starting above the previous row's end — mean the matrix read row by row is one long sorted list. So run an ordinary binary search over the virtual index range [0, m*n) and translate each index back to a cell with a divide and a modulo.

Approach

1. Treat the matrix as a flat list of m * n values.
2. Binary search k over [0, m*n - 1].
3. Map k to a cell: row k / cols, column k % cols.
4. Compare and halve the range exactly as in a one-dimensional binary search.
5. Return whether the target was found.

Why it works

The row-boundary condition is what makes the flattening valid: without it, rows could overlap in value and the concatenation would not be sorted. With it, reading in row-major order yields a strictly increasing sequence, so the standard invariant holds and one search over log(m*n) steps suffices — better than a per-row search, which costs O(m + log n) or O(m log n) depending on how it is done.

Complexity

• Time — O(log(m·n))
• Space — O(1)

Pitfalls

• The index mapping divides and mods by the column count, not the row count.
• This flattening is only sound because of the "first of each row exceeds last of the previous" guarantee; a merely row-sorted matrix needs the staircase walk from the top-right corner instead.
• The upper bound is m*n - 1 for an inclusive search; using m*n with lo <= hi reads out of bounds.
• Compute m*n in a type wide enough for large matrices.

Reference solution

Python

from typing import List

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
        v = matrix[mid // n][mid % n]
        if v == target:
            return True
        if v < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False

Java

public static boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length, cols = matrix[0].length;
    int lo = 0, hi = rows * cols - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int v = matrix[mid / cols][mid % cols];
        if (v == target) return true;
        if (v < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

C++

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = (int) matrix.size(), cols = (int) matrix[0].size();
    int lo = 0, hi = rows * cols - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int v = matrix[mid / cols][mid % cols];
        if (v == target) return true;
        if (v < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

JavaScript

var searchMatrix = function(matrix, target) {
    const m = matrix.length, n = matrix[0].length;
    let lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        const v = matrix[Math.floor(mid / n)][mid % n];
        if (v === target) return true;
        if (v < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium