前言
二分查找这个算法相信大家都很熟悉，但真正在写代码的时候，对于边界条件却很容易出错，这篇文章带你分析二分查找的关键细节，看完以后不再出错。
题目
虽然都是二分查找，但其实题目可能会有细微的差别。
这里先统一一下题目：给定非严格递增的列表nums，给定x，找出其中最小值i，满足nums[i] >= x。
也就是说，如果存在多个x，则返回第一个的下标；如果不存在x，则返回大于x的下标。
代码
这里展示两段代码，看看两者的差别，你认为哪个正确，哪个错误呢：
代码1
func find(nums []int, x int) int {
i, j := 0, len(nums)
var m int
for i < j {
m = i + (j-i)/2
if nums[m] >= x {
j = m
} else {
i = m+1
}
}
return i
}
代码2
func find(nums []int, x int) int {
i, j := 0, len(nums)-1
var m int
for i <= j {
m = i + (j-i)/2
if nums[m] >= x {
j = m-1
} else {
i = m+1
}
}
return i
}
注意两者的差别：
- 初始赋值不同，一个是
j = len(nums)，另一个是j = len(nums)-1 - 循环条件不同，一个是
i < j，另一个是i <= j - j每次的变化不同，一个是
j = m，另一个是j = m-1
你觉得哪一种才是正确的呢？
实际上，两种都是正确的，只不过这两段代码中，j永远相差了1而已。这也导致结束后，i和j的状态不同。代码1中结束时，i == j；而代码2中结束时i = j+1，记得一定要返回i，不要返回j。
但两种不能混用，如果循环条件是i <= j，而j的迭代是j = m，则可能会造成死循环。
你可能有疑问，为什么j有两种迭代方式，而i只有一种？能不能每次迭代让i = m？这当然不行，因为i和j本来就不是对等的，原因就在于m：i <= m < j，所以迭代部分如果改成i = m可能会陷入死循环。
判断条件抽象
然后你可能要问了，如果nums数组不是递增而是递减的怎么办？如果题目改成要找的是第一个nums[m] > x 的下标，而不是nums[m] >= x怎么办？
其实我刚开始也会在边界条件纠结很久，条件稍一变化就又要重新思考，但这归根结底还是对问题思考的不够透彻，没有把问题抽象出来。
实际上，我们看代码里，只有两个地方用到了nums，其中一个是用到其长度，另一个就是判断条件。也就是说，其实二分查找根本不需要知道nums数组本身，只要知道其长度，并且能够判断是否满足条件即可。
于是我们的代码可以变成这样：
代码3
func Search(n int, f func(int) bool) int {
i, j := 0, n
for i < j {
h := int(uint(i+j) >> 1)
if !f(h) {
i = h + 1
} else {
j = h
}
}
return i
}
只需要传入长度和一个判断函数，就可以找到第一个满足条件的值的下标。当然，判断函数f是有约束的：如果f(i) == false, f(j) == true，那么必须满足 i < j。简单说就是左边是false，右边是true。
显然，对于文章开头描述的题目，可以这样去调用：
代码4
func SearchInts(a []int, x int) int {
return Search(len(a), func(i int) bool { return a[i] >= x })
}
实际上，这两段代码，正是golang里面官方sort包下面的函数。
这样一抽象，问题也就看得更加透彻了，题目再怎么变化，只要修改这个判断函数f就可以了。
总结
这篇文章主要讲了关于二分查找的两个点：
- i每次迭代都是
i = m + 1，而j在两种实现里分成两档，涉及到3个地方，别混用就行。 - 函数要返回i，不要返回j（j不一定错，但i一定对）。
- for循环中的if判断条件，根据题目进行修改即可，代码最终找到的都是“第一个满足该条件的下标”
好了，以后无论遇到二分查找的什么变种，都能顺利解决啦！
网友评论