74.M 搜索二维矩阵

题目

https://leetcode-cn.com/problems/search-a-2d-matrix/

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。

示例 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

提示：

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 100

• -104 <= matrix[i][j], target <= 104

解题思路

二分查找。

把每一行拼接到上一行的末尾，就可以得到一个一维的递增序列，对这个递增序列进行二分查找即可。与普通二分查找的区别是，需要把mid映射为行号和列号。

实现代码

func searchMatrix(matrix [][]int, target int) bool {
	rows := len(matrix)
	cols := len(matrix[0])
	left := 0
	right := rows * cols - 1
	for left <= right {
		mid := left + (right - left) / 2
		row := mid / cols
		col := mid % cols
		if matrix[row][col] == target {
			return true
		} else if matrix[row][col] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return false
}