Search a Sorted 2D Matrix

medium binary search matrix

Problem

An m × n matrix has every row sorted left-to-right and the first cell of each row is greater than the last cell of the previous row — so reading it row-by-row gives one fully sorted sequence of length m·n. Decide whether a target value lives somewhere in the matrix.

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

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