Go标准库sort.Search是这样实现的二分查找

前言

哈喽，大家好，我是asong。今天与大家分享一下Go标准库sort.Search是如何实现二分查找的，为什么突然想到分享这个函数呢。起因是这周在刷leetcode的一道题时，需要使用到二分查找，最开始是自己实现了一版，后面就想Go语言标准库这么全，应该会有这个封装，果然被我找到了，顺便看了一下他是怎么实现的，感觉挺有意思的，就赶紧来分享一下。
小声逼逼一下，最近有读者反馈说最近发文不够频繁，在这里同步一下我最近干什么：
工作太忙了
正在写一个本地缓存，后面会分享出来
正在筹备我的第一个开源项目，敬请期待

什么是二分查找

以下来自百度百科：

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

总结一下，使用二分查找必须要符合两个要求：

必须采用顺序存储结构
必须按关键字大小有序排列

我们来举个例子，就很容易理解了，就拿我和我女朋友的聊天内容做个例子吧：

我家宝宝每次买一件新衣服，就会习惯性的问我一句，小松子，来猜一猜我这次花了多少钱？
小松子：50？
臭宝：你埋汰我呢？欠打！
小松子：500？
臭宝：你当我是富婆呢？能不能有点智商！
小松子：250？
臭宝：我感觉你在骂我，可我还没有证据。少啦，少啦！！！
小松子：哎呀，好难猜呀，290？
臭宝：啊！你这臭男人，就是在骂我！气死啦，气死啦！多啦，多啦！
小松子：难道是260？
臭宝：哎呦，挺厉害呀，竟然猜对了！
后面对话内容就省略啦.....

这里我只需要5次就成功猜出来了，这就是二分查找的思想，每一次猜测，我们都选取一段整数范围的中位数，根据条件帮我们逐步缩小范围，每一次都以让剩下的选择范围缩小一半，效率提高。

二分查找的时间复杂度

二分查找每次把搜索区域减少一半，时间复杂度为O(logn)。（n代表集合中元素的个数）。

空间复杂度为O(1)。

自己实现一个二分查找

二分算法的实现还是比较简单的，可以分两种方式实现：递归和非递归方式实现，示例代码如下：

非递归方式实现：

// 二分查找非递归实现
func binarySearch(target int64, nums []int64) int {
   left := 0
   right := len(nums)
   for left <= right {
      mid := left + (right - left) / 2
      if target == nums[mid] {
         return mid
      }
      if target > nums[mid] {
         left = mid + 1
         continue
      }
      if target < nums[mid] {
         right = mid - 1
         continue
      }
   }
   return -1
}

总体思路很简单，每次我们都选取一段整数范围的中位数，然后根据条件让剩下的选择范围缩小一半。这里有一个要注意的点就是我们在获取中位数时使用的写法是 mid := left + (right - left) / 2，而不是mid = （left +right）/2的写法，这是因为后者有可能会造成位数的溢出，也就会导致结果出问题。

递归方式实现：

func Search(nums []int64, target int64) int {
    return binarySearchRecursive(target, nums, 0, len(nums))
}

func binarySearchRecursive(target int64, nums []int64, left, right int) int {
    if left > right {
        return -1
    }

    mid := left + (right - left) / 2

    if target == nums[mid] {
        return mid
    }
    if nums[mid] < target {
        return binarySearchRecursive(target, nums, mid+1, right)
    }
    if nums[mid] > target {

        return binarySearchRecursive(target, nums, left, mid-1)
    }
    return -1

}

Go标准库是如何实现二分查找的？

我们先看一下标准库中的代码实现：

func Search(n int, f func(int) bool) int {
    // Define f(-1) == false and f(n) == true.
    // Invariant: f(i-1) == false, f(j) == true.
    i, j := 0, n
    for i < j {
        h := int(uint(i+j) >> 1) // avoid overflow when computing h
        // i ≤ h < j
        if !f(h) {
            i = h + 1 // preserves f(i-1) == false
        } else {
            j = h // preserves f(j) == true
        }
    }
    // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
    return i
}

初一看，与我们上面的实现一点也不同呢，我们来分析一下。

入参n就是代表要查找序列的长度，入参f就是我们自定义的条件。这段代码很短，大概思路就是：

定义好这段序列的开始、结尾的位置
使用位移操作获取中位数，这样能更好的避免溢出
然后根据我们传入的条件判断是否符合条件，逐渐缩小范围

这段代码与我实现的不同在于，它并不是在用户传入的比较函数f返回true就结束查找，而是继续在当前[i, j)区间的前半段查找，并且，当f为false时，也不比较当前元素与要查找的元素的大小关系，而是直接在后半段查找。所以for循环退出的唯一条件就是i>=j，如果我们这样使用，就会出现问题：

func main() {
    nums := []int64{1, 2, 3, 4, 5, 6, 7}
    fmt.Println(sort.Search(len(nums), func(i int) bool{
        return nums[i] == 1
    }))
}

运行结果竟然是7，而不是1，如果我们把条件改成return nums[i] >=1，运行结果就对了。这是因为我们传入的条件并不是让用户确认目标条件，这里的思想是让我们逐步缩小范围，通过这个条件，我们每次都可以缩小范围，说的有点饶，就上面的代码举个例子。现在是一个升序数组，我们要找的数值是1，我们传入的条件是return nums[i]>=1，第一进入函数Search，我们获取中的中位数h是3，当前元素是大于目标数值的，所以我们只能在前半段查找，就是这样不断缩小范围，找到我们最终的那个数值，如果当前序列中没有我们要找的目标数值，那么就会返回我们可以插入的位置，也就是最后一位元素的坐标+1的位置。

这个逻辑说实话，我也是第一次接触，仔细思考了一下，这种实现还是有一些优点的：