题目链接：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
}
