二分查找
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
题目链接
示例 1:

  1. 输入:
  2. matrix = [
  3.  [1,   3,  5,  7],
  4.  [10, 11, 16, 20],
  5.  [23, 30, 34, 50]
  6. ]
  7. target = 3
  8. 输出: true

Binary Search

  1. 两次二分查找，先用二分查找目标所在行，然后在所在行中继续二分
  2. 注意查找所在行[up, down]时，用本行中最后的值和target比较
    1. target > nums[mid]时，在（mid, down]区间， 左开又闭
    2. target < nums[mid] 时，相反在[up, mid] 闭区间，因为可能在本行，所以Mid侧为闭区间
    • golang
      1. func searchMatrix(matrix [][]int, target int) bool {
      2. if len(matrix) == 0 {
      3. return false
      4. }
      5. col := len(matrix[0]) //列
      6. row := len(matrix)    //行
      7. up := 0               
      8. down := row - 1
      9. var mid int
      10. for up < down {       //二分查找所在行
      11. mid = up + ((down - up) >> 1)
      12. if target > matrix[mid][col-1] { //目标比中间值大，则移上边界 (mid, down]
      13.     up = mid + 1
      14. }else {          //目标比中间值小结果在[up, mid]之间
      15.     down = mid   //不能减一，可能在本行
      16. }   
      17. }                   //最终up和down在同一行
      18. left := 0
      19. right := col - 1
      20. for left <= right {
      21. mid := left + ((right - left) >> 1)
      22. if target == matrix[up][mid] {
      23.     return true
      24. }
      25. if target < matrix[up][mid] {
      26.     right = mid - 1
      27. }else {
      28.     left = mid + 1
      29. }
      30. }
      31. return false
      32. }