这是索引二分的第五篇算法，力扣链接
给你一个满足下述两条属性的
m x n整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数
target，如果target在矩阵中，返回true；否则，返回false。示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 输出：true
这道题在之前的专栏其实讲过，这里在这里复习一下。
老规矩，先上暴力求解，具体怎么暴力呢？先确定数据在第几行，怎么确定呢？
matrix[x+1][len(matrix[0]-1] > target > matrix[x][len(matrix[0]-1]
然后再在该行暴力查找，直接上代码：
func searchMatrix(matrix [][]int, target int) bool {
x := -1
for i := 0; i < len(matrix); i++ {
if matrix[i][len(matrix[i])-1] >= target {
x = i
break
}
}
if x == -1 {
return false
}
for i := 0; i < len(matrix[0]); i++ {
if matrix[x][i] == target {
return true
}
}
return false
}
当然，我们可以在一行内用二分法查找：
func searchMatrix(matrix [][]int, target int) bool {
x := -1
for i := 0; i < len(matrix); i++ {
if matrix[i][len(matrix[i])-1] >= target {
x = i
break
}
}
if x == -1 {
return false
}
l, r := 0, len(matrix[x])-1
for l <= r {
mid := l + (r-l)/2
if matrix[x][mid] == target {
return true
}
if matrix[x][mid] < target {
l = mid + 1
} else {
r = mid - 1
}
}
return false
}第一步暴力逻辑也可以改为二分查找：
func searchMatrix(matrix [][]int, target int) bool {
l, r := 0, len(matrix)-1
for l <= r {
mid := l + (r-l)/2
if matrix[mid][0] == target {
return true
}
if matrix[mid][0] < target {
l++
} else {
r--
}
}
if r < 0 {
return false
}
x := r
l, r = 0, len(matrix[x])-1
for l <= r {
mid := l + (r-l)/2
if matrix[x][mid] == target {
return true
}
if matrix[x][mid] < target {
l = mid + 1
} else {
r = mid - 1
}
}
return false
}如果将每一行都接在前一行的末尾，那么将是一个一维的有序数组：
func searchMatrix(matrix [][]int, target int) bool {
h, w := len(matrix), len(matrix[0])
l, r := 0, h*w-1
for l <= r {
mid := l + (r-l)/2
if matrix[mid/w][mid%w] == target {
return true
}
if matrix[mid / w][mid % w] < target {
l++
}else {
r--
}
}
return false
}这终究都属于暴力解法，我们可以试试Z字查找，从[0][len(maxtrix[0]]开始，大了就往左移动，小了就往右移动。
func searchMatrix(matrix [][]int, target int) bool {
h, w := 0, len(matrix[0])-1
for h < len(matrix) && w >= 0 {
if matrix[h][w] == target {
return true
}
if matrix[h][w] > target {
w--
} else {
h ++
}
}
return false
}
