福哥答案2020-11-15：
此题来源于leetcode240和剑指 Offer（第 2 版）面试题4。
1.线性查找。
从二维数组的坐下角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则上移。如果当前元素小于目标值，则右移。
2.线性查找+二分查找。
当前元素上移和右移，采用二分法。要用到如下两道题：
2.1.在一个有序数组中，找<=某个数最右侧的位置。
2.2.在一个有序数组中，找>=某个数最左侧的位置。
golang代码如下：
package main import "fmt" //https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
//https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
func main() {
matrix := [][]int{
{1, 4, 7, 11, 15},
{2, 5, 8, 12, 19},
{3, 6, 9, 16, 22},
{10, 13, 14, 17, 24},
{18, 21, 23, 26, 30},
}
target := 15
fmt.Println("线性查找：", findNumberIn2DArray1(matrix, target))
fmt.Println("线性查找+二分查找：", findNumberIn2DArray2(matrix, target))
} //线性查找
func findNumberIn2DArray1(matrix [][]int, target int) bool {
N := len(matrix)
if N == 0 {
return false
}
M := len(matrix[0])
n := N - 1
m := 0
for n >= 0 && m < M {
if matrix[n][m] > target { //如果当前元素大于目标值，则上移
//↑
n--
} else if matrix[n][m] < target { //如果当前元素小于目标值，则右移
//→
m++
} else {
return true
}
}
return false
} //线性查找+二分查找
func findNumberIn2DArray2(matrix [][]int, target int) bool {
N := len(matrix)
if N == 0 {
return false
}
M := len(matrix[0])
n := N - 1
m := 0
for n >= 0 && m < M {
if matrix[n][m] > target { //在一个有序数组中，找<=某个数最右侧的位置
//↑
//n--
UP := 0
DOWN := n
index := -1
for UP <= DOWN {
mid := UP + (DOWN-UP)>>1
if matrix[mid][m] == target {
return true
} else if matrix[mid][m] < target {
index = mid
UP = mid + 1
} else {
DOWN = mid - 1
}
}
if index == -1 {
return false
} else {
n = index
} } else if matrix[n][m] < target { //在一个有序数组中，找>=某个数最左侧的位置
//→
//m++
LEFT := m
RIGHT := M - 1
index := -1
for LEFT <= RIGHT {
mid := LEFT + (RIGHT-LEFT)>>1
if matrix[n][mid] == target {
return true
} else if matrix[n][mid] > target {
index = mid
RIGHT = mid - 1
} else {
LEFT = mid + 1
}
}
if index == -1 {
return false
} else {
m = index
}
} else {
return true
}
}
return false
}
执行结果如下：
