LeetCode-74. 搜索二维矩阵 - sheep44044的小站

二分查找#

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

每行中的整数从左到右按非严格递增顺序排列。

每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例 1：

1
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
2
输出：true

示例 2：

1
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
2
输出：false

手撕

思路: 这题可以看作长度为 m*n 的数组，只需要把mid转换为对应矩阵的row和col即可，其他与 35. 搜索插入位置 类似

1
func searchMatrix(matrix [][]int, target int) bool {
2
    m, n := len(matrix), len(matrix[0])
3
    left, right := 0, m*n-1
4
    var mid, row, col int
5

6
    for left <= right {
7
        mid = left + (right - left)/2
8
        row = mid / n
9
        col = mid % n
10

11
        if matrix[row][col] == target {
12
            return true
13
        }else if matrix[row][col] < target {
14
            left = mid + 1
15
        }else {
16
            right = mid - 1
17
        }
18
    }
19
    return false
20
}