搜索二维矩阵I

74. 搜索二维矩阵

题目：给你一个满足下述两条属性的 m x n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例1:
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true 示例2:
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

解题思路

二分法: 二分查找行、二分查找列。注意点，查找行时，如果等于某行第一个元素，找到目标如果大于某行第一个元素，继续往下寻找如果小雨某行第一个元素，停止搜索，并且往上一行寻找所以最终right 就是该目标所在的行索引。
利用从左到右，从上到下递增的矩阵特性，从右上角开始搜索，小于往左找，大于往下找

解法一

func searchMatrix(matrix [][]int, target int) bool {
	  m := len(matrix)
	  if m == 0 {
	  	return false
	  }
	  n := len(matrix[0])
	  if n == 0 {
	  	return false
	  }
      
	  // 行二分
	  var left, right = 0, m - 1
	  for left <= right {
	  	mid := (left + right) / 2
	  	if target > matrix[mid][0] {
	  		left = mid + 1
	  	} else if target < matrix[mid][0] {
	  		right = mid - 1
	  	} else {
	  		return true
	  	}
	  }
      
	  // 如果等于某行第一个元素，找到目标
	  // 如果大于某行第一个元素，继续往下寻找
	  // 如果小雨某行第一个元素，停止搜索，并且往上一行寻找
	  // 所以 最终right 就是该目标所在的行索引
	  if right < 0 {
	  	return false
	  }
      
	  row := right
	  // 二分查找列
	  l, r := 0, n-1
	  for l <= r {
	  	mid := (l + r) / 2
	  	if target > matrix[row][mid] {
	  		l = mid + 1
	  	} else if target < matrix[row][mid] {
	  		r = mid - 1
	  	} else {
	  		return true
	  	}
	  }
	  return false
}

解法二

func searchMatrix1(matrix [][]int, target int) bool {
	  m := len(matrix)
	  if m == 0 {
	  	return false
	  }
	  n := len(matrix[0])
	  if n == 0 {
	  	return false
	  }
	  var row, col = 0, n - 1
	  for col >= 0 && row < m {
	  	if matrix[row][col] == target {
	  		return true
	  	} else if matrix[row][col] > target {
	  		col--
	  	} else {
	  		row++
	  	}
	  }
      
	  return false
}

cs-book

74. 搜索二维矩阵