题目链接：74

思路

由题意可知：每一行的第一个元素都比上一行的第一列元素大，也即第一列是递增的。因此可以使用两次binary search来找到答案。

首先对第一列进行binary search，找出第一列中不大于 target 的最大的元素；然后对该元素所在的行进行 binary search，找出是否存在 target。

// 1. do binary search on first column, find the biggest element that is not bigger than target;
// 2. do binary search on the row of the element, find whether target exist
func searchMatrix(matrix [][]int, target int) bool {
    // 1.
    left, right := 0, len(matrix) - 1
    for left < right - 1 {
        mid := left + (right - left) / 2
        if matrix[mid][0] <= target {
            left = mid
        } else {
            right = mid - 1
        }
    }
    var eleR int
    if matrix[left][0] > target {
        return false
    } else if matrix[right][0] <= target {
        eleR = right
    } else {
        eleR = left
    }

    // 2.
    left, right = 0, len(matrix[eleR]) - 1
    for left <= right {
        mid := left + (right - left) / 2
        if matrix[eleR][mid] == target {
            return true
        } else if matrix[eleR][mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}