源码，是最好的学习资料。
之前做二分查找没有一个方法准则，总是现抠代码实现的，对于边界情况总是把握不准，知道它是有一定准则的，但总是疏于整理。后来看到 go 的 sort 包中有实现二分查找算法，非常简洁，所以这里设计思路分析一波（自己再也不怕手撕二分了）。
go 源码 sort.Search
sort.Search(n int, f func(int) bool)
源码 sort.Search() 给出了使用准则：
- 第一个参数 n 表示数列元素个数
- 第二个参数为闭包函数
f func(i int) bool - sort.Search 方法查找的就是满足函数
f(i) == true的第一个下标位置 k，所以对 f 函数有约定满足公式：f(i) == false, (i < k) f(i) == true, (i >= k)
sort.Search 的实现思路
为了更好的解释，这里不是 copy 的源码。而是一个普通的二分查找算法寻找 target 的下标或可插入的位置坐标。这可以是自己实现的一个模板。
所有的二分查找都可以转换成这个查找：查找符合条件的第一个元素的下标 k。这个条件 f 满足：当 i < k 时，f(i) == false；当 i >= k 时，f(i) == true。
用二分的前提是数列一定是有序的，这不再多解释。
由上条件我们可以将这个数列简化为 [false, false, true, true, true]，即找第一个为 true 的下标。
二分法的最基本的模板应该是这样：
for FOR_COND:
mid = (left + right) / 2 // 取得中间点
if cond(mid):
right = NEXT_RIGHT // 动 right
else
left = NEXT_LEFT // 动 left
但细节就在模板里的三个占位语句上。如 FOR_COND 该选择 left < right 还是 left <= right？NEXT_RIGHT 或 NEXT_LEFT 应该是 mid±1 还是 mid。
这里我们将
left = left + 1称为“left 向前游走一次”；right = right - 1称为 “right 向后游走一次”。每次mid = (left + right) / 2后，mid 总要替换 left 或 right，即若替换 left 时可以为left = mid就是说“不游走”，若为left = mid + 1就是说“left 游走一次”。即可发现：
- 让 left 游走，就可能让 left 从指向 false 变为指向 true
- 让 right 游走，就可能让 right 从指向 true 变为指向 false
所以，NEXT_LEFT 的条件其实主要就是上述两种影响。
考虑
- 在
mid = (left + right) / 2的计算中，left != right时，mid是有可能等于left而不可能等于right。 - 而上述中排除的
left == right条件正好可以做终止循环的条件。
所以，
- 由第一个条件，我们最好让 left 游走，而 right 永远指向 true 的位置最好了。
- 即 NEXT_RIGHT 处为
right = mid；NEXT_LEFT 处为left = mid + 1 - 这时，FOR_COND 就可以是
left < right - 由于 right 永远指向 true 的位置，为了避免全数列都是 false 的情况，我们让 right 最初为 n（n 为数列长度），即假设了
f(n) == true - 同时注意，数列全为 false 时，返回的下标是 n，是数列溢出的下标位置。
综上，我们可以写出一下模板：
func binarySearch:
left, right = 0, n
for left < right:
mid = left + (right - left) / 2 // 防溢出
if cond(mid):
left = mid + 1
else
right = mid
// 最终得到 left 值为第一个满足 cond 的位置（注意可能为 n）
练习题
由上拿 力扣：35. 搜索插入位置 （找到 target 可插入的位置）为例，不难写出如下代码：
func searchInsert(nums []int, target int) int {
cond := func(i int) bool { return nums[i] >= target }
left := 0
right := len(nums) // right may not idx
for left < right { // stop when left == right
mid := left + (right-left)/2 // mid could be left but won't be right, if left != right
if cond(mid) {
right = mid // right is always hit the cond
} else {
left = mid + 1 //
}
}
return left
}
力扣：278. 第一个错误的版本 更像是进一步让自己设计出 sort.Search 的代码出的题：
// var isBadVersion func(i int) bool // 力扣的伪代码
func firstBadVersion(n int) int {
left:= 0
right:= n
for left < right {
mid:= left + (right - left) / 2
if isBadVersion(mid) {
right = mid
}else {
left = mid + 1
}
}
return left
}
总结
可见，你可以通过变更上述的 cond 函数（必须满足前面都是 false，后面都是 true），来查找到合适的点（第一个使 cond(i) == true 的位置点 k）
香饽饽
go 包的 sort.Search 真实太香了。下面的题看到题后直接抠码三分钟就完成。
可见，熟悉内置的一些算法方法，可以让做题效率提升很多。力扣竞赛中常常有 20 分钟内做完四道题的人，可想而知。
- 力扣中等题 162. 寻找峰值
func findPeakElement(nums []int) int {
switch len(nums) {
case 1:
return 0
case 2:
if nums[0] > nums[1] {
return 0
}
return 1
}
x := sort.Search(len(nums)-1, func(i int) bool {
switch i {
default:
return nums[i]-nums[i+1] > 0
}
})
return x
}
- 力扣中等题 153. 寻找旋转排序数组中的最小值
func findMin(nums []int) int {
if len(nums) == 0 {
return nums[0]
}
x := sort.Search(len(nums), func(i int) bool {
return nums[i] < nums[0]
})
if x < len(nums) {
return nums[x]
}
return nums[0]
}
网友评论