前言

二分查找这个算法相信大家都很熟悉，但真正在写代码的时候，对于边界条件却很容易出错，这篇文章带你分析二分查找的关键细节，看完以后不再出错。

题目

虽然都是二分查找，但其实题目可能会有细微的差别。
这里先统一一下题目：给定非严格递增的列表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
}

注意两者的差别：

1. 初始赋值不同，一个是j = len(nums)，另一个是j = len(nums)-1
2. 循环条件不同，一个是i < j，另一个是 i <= j
3. 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就可以了。

总结

这篇文章主要讲了关于二分查找的两个点：

1. i每次迭代都是i = m + 1，而j在两种实现里分成两档，涉及到3个地方，别混用就行。
2. 函数要返回i，不要返回j（j不一定错，但i一定对）。
3. for循环中的if判断条件，根据题目进行修改即可，代码最终找到的都是“第一个满足该条件的下标”

好了，以后无论遇到二分查找的什么变种，都能顺利解决啦！