74. Search a 2D Matrix

search-a-2d-matrix.go

// https://leetcode.com/problems/search-a-2d-matrix/
//
// Time:  O(log(m*n))
// Space: O(1)
//
// m = number of rows
// n = number of columns

// .................... //

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    lo, hi := 0, m*n-1

    for lo <= hi {
        mi := lo + (hi-lo)/2

        row, col := mi/n, mi%n
        candidate := matrix[row][col]

        if candidate == target {
            return true
        }

        if candidate > target {
            hi = mi - 1
        } else {
            lo = mi + 1
        }
    }

    return false
}