Search a 2D Matrix

Problem Summary

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

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

Constraints:

Both m (rows) and n (columns) are between 1 and 100.
Each element and the target are integers in the range [-10,000, 10,000].

Techniques

Array
Binary Search
Matrix

Solution

function searchMatrix(matrix: number[][], target: number): boolean {
    let m = matrix.length
    let n = matrix[0].length
    let cells = m * n
    let left = 0
    let right = cells - 1

    while (left <= right) {
        let mid = left + Math.floor((right - left) / 2)
        let currentM = Math.floor(mid / n)
        let currentN = mid % n

        if (matrix[currentM][currentN] === target) {
            return true
        }

        if (matrix[currentM][currentN] > target) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return false
}

console.log(searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3)) // true
console.log(searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13)) // true