前言
真菜的我。
正文
问题来源
本问题来自leetcode上的240题。用go语言做的
问题描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
示例 :
输入:
[
[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 = 5，返回 true。
若给定 target = 20，返回 false。
分析：
本人的想法是采用逐行二分搜索来查找。 本人写的Go代码如下：
func binary_search(array []int,target int) bool {
l := len(array)
left, right := 0, l-1
mid := (left+right) / 2
if 0 == l {
return false
}
for ;left <= right ; mid = (left+right)/2 {
cur := array[mid]
if cur == target {
return true
} else if cur > target {
right = mid - 1
} else {
left = mid + 1
}
}
return false
}
func searchMatrix(matrix [][]int, target int) bool {
l := len(matrix)
if 0 == l {
return false
}
for i := 0; i < l; i++ {
if binary_search(matrix[i], target) {
return true
}
}
return false
}
这题的思路很简单，利用矩阵行列分别有序的性质，我们从第0行的最右端开始搜索，两种情况：
- 如果当前的数比target大，则说明target必然在target的左边，则搜索其左边的位置
- 如果当前的数比target小，则说明和target相等的数必然不在这一行，因此往下一行搜索。
- 如果当前的数和target相等，则说明找到了这个target
func searchMatrix(matrix [][]int, target int) bool {
n := len(matrix)
if n <= 0 {
return false
}
m := len(matrix[0])
if m <= 0 {
return false
}
for i, j := 0, m - 1; i < n && j >= 0; {
num := matrix[i][j]
if num == target {
return true
} else if num < target {
i++
} else {
j--
}
}
return false
}
总结：
勤思考
结语
不管怎么样好好加油。
