Search a 2D Matrix

MediumBinary Search

Search a value in an m x n matrix where each row is sorted and the first integer of each row is greater than the last of the previous row.

Open problem

Constraints

1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4

Binary search on the flattened matrix

Time O(log(m*n))Space O(1)

Because rows are sorted and chained, the matrix behaves like one sorted array of length m*n. Binary search over indices and map each index to row and column.

#include <bits/stdc++.h>
using namespace std;

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;
}