Search a 2D Matrix

medium binary search matrix

Problem

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

Inputmatrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 11

Outputtrue

Imagine the matrix flattened: index k maps to row = ⌊k/n⌋, col = k mod n. Binary-search k in [0, m·n − 1].

matrix (rows separated by ;)

target

def search_matrix(matrix, target):
    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

function searchMatrix(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[(mid / n) | 0][mid % n];
    if (v === target) return true;
    if (v < target) lo = mid + 1; else hi = mid - 1;
  }
  return false;
}

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

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

Explanation

Here every row is sorted and each row starts higher than the previous row ends. That means if you read the matrix row by row, the values form one big sorted sequence — so we can run an ordinary binary search over it.

The trick is to pretend the matrix is a flat array of length m * n without actually flattening it. A flat index k maps back to a cell by row = k / n and col = k % n, where n is the number of columns.

We binary search on k in [0, m*n - 1]. At each step we compute mid, convert it to its (row, col), read the value, and compare to the target: if smaller, move lo = mid + 1; if larger, move hi = mid - 1; if equal, return true.

Example: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target 11. With n = 4, index 5 maps to row 5/4 = 1, col 5%4 = 1, which is matrix[1][1] = 11. Match.

Because we only ever look at one cell per step and halve the range each time, the search costs about log(m*n) — the speed of binary search without building any extra array.

Time: O(log(m·n)) Space: O(1)