vlambda博客
学习文章列表

"老弟在吗，我怀疑 Go 标准库中的二分查找有 bug！"
"老哥别慌，源码之前没有秘密，你坐下听我吹吹c++的牛逼。。"

下面这段 Go 代码，你觉得 index 的结果是多少？

arr := []int{1, 3, 5, 7}
index := sort.Search(len(arr), func(i int) bool {
    return arr[i] == 3
})

index 的结果并不是 1，而是 4。（额，返回 4 是什么鬼，难道不应该找到就返回对应的下标，找不到就返回-1 吗）

我们映象中的二分是这样的：

while (low <= high) {
    mid := (low + high) / 2
    if arr[mid] < target {
        low = mid + 1
    } else if arr[mid] > target {
        high = mid - 1
    } else {
        return mid
    }
}

标准库中的 sort.Search 是这样的：

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
}

乍一看，sort.Search 像是个二分查找的实现。

但它并不是用户传入的比较函数 f 返回 true 就结束查找，而是继续在当前[i, j)区间的前半段查找。

并且，当 f 为 false 时，也不比较当前元素与要查找的元素的大小关系，而是直接在后半段查找。

for 循环退出的唯一条件是i >= j。

后文为了方便描述，对名词做个统一。target表示要查找的值，也即上面的 3。

我们先贴上正确的用法，接着分析：

index := sort.Search(len(arr), func(i int) bool {
    // return arr[i] == 3
    return arr[i] >= 3
})

函数 f 并不是让用户指定== target的规则，而是上层和下层一块配合：

当前元素<target，那么必然当前元素之前的元素也<target（因为是升序数组），所以只用在后半段查找。

当前元素>=target，那么当前元素之前的元素和 target 的大小不确定；当前元素之后的元素也必然>或者==target。此时，Search 只在前半段找。

你仔细想想，就会发现，这种查找方式有一些好处：

1. 当有多个元素都等于 target 时，实际上可以找到下标最小的那个元素
2. 当 target 不存在时，返回的下标标识了如果要将 target 插入，插入的位置（插入后依然保持数组有序）
3. 基于这种编程范式，上层只用提供一个与自身数据类型相关的比较函数

sort.Search 返回值的正确食用方式：判断 index 在 len 的范围内，并且 index 位置的元素的值又和想要查找的值相等，也即index < len(arr) && arr[index] == target，条件满足则说明找到，返回的是下标，条件不满足则说明没找到，返回的是可以插入的位置。

另外，我们上面的例子，数组是升序排序的，如果数组是降序，那么函数 f 应该使用<=。

另外，sort.Search 中还有一个小细节，h := int(uint(i+j) >> 1)，这里先转换成 uint 相加再取半，可以防止两个 int 相加溢出。

算法部分再多说一句，实际上函数 f 和函数 Search 是一个完整的算法逻辑，只是 API 为了提供抽象，强行将逻辑切割开了，如果你之前没接触过这种二分算法的思想，光看 Search 的实现，不看函数 f 的实现，确实有点容易搞晕。

好，到这，算法部分讲完了，接下来我们来聊聊 Go 和c++的编程范式，也即它们是如何对数据类型做抽象，提供 API 的。

sort.Search 的函数 f 可以看成是一个回调函数，它只接收下标参数，而不是接收和类型相关的数组作为参数，上层提供函数 f 的实现中，直接使用了外层的数组变量，实际上是使用了 Go 闭包的特性。

那么假设我想直接提供面向一些基础类型的查找函数，不再由上层提供函数 f 呢？事实上 sort 包还真提供了：

// - 只需传入整型切片和target
// - 注意，该函数只能对升序数组做查找
func SearchInts(a []int, x int) int {
    return Search(len(a), func(i int) bool { return a[i] >= x })
}

func SearchFloat64s(a []float64, x float64) int {
    return Search(len(a), func(i int) bool { return a[i] >= x })
}
func SearchStrings(a []string, x string) int {
    return Search(len(a), func(i int) bool { return a[i] >= x })
}

但是，由于函数 f 的实现需要访问数组，并且做运算符>=的比较，也即必须知道数组的类型，也即提供给上层的函数也必须传入具体类型的数组，所以 sort 包提供了三个面向基础类型的函数，看函数的签名，只是切片类型不同，里面的实现是一模一样的。。

假如是其他基础类型呢，比如 int64，float32 等等，对不起，没有。。想要？继续ctrl+cv。。

另外，由于 Go 不支持函数重载，所以这三个函数名字不能一样，必须加后缀。。

sort 包还提供给上层另外一种使用方式：

type IntSlice []int
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }

这种方式，方法名倒是相同了，但是参数类型不同，也即签名依然不一致，所以你也没法适配同一个type xxx interface。。并且，也只给你写了 3 个。。

还有一点不得不提，事实上，Go 可以基于 interface{}，对类型做抽象，提供统一接口，由内部判断类型。但是这种方式会增加运行时开销。。

最后，我们去看一眼c++标准库 STL 中二分查找的接口设计。std::binary_search函数声明如下：

template <class ForwardIterator, class T>
 bool binary_search (ForwardIterator first, ForwardIterator last,
 const T& val);

template <class ForwardIterator, class T, class Compare>
 bool binary_search (ForwardIterator first, ForwardIterator last,
 const T& val, Compare comp);

可以看到，通过函数重载，提供了两个函数。

函数重载是语法糖，编译时会生成不同的函数，只不过对写代码的人是无感知的。

我们先看第一个，c++通过模板手法，所有支持比较运算符的基础类型都可以直接使用这个函数。并且非基础类型也可以通过重载比较运算符的方式，直接使用第一个函数。

模板是在编译时通过模板和带有具体类型的使用模板的代码生成模板对应的具体代码。

运算符重载，是为自定义类型添加运算符成员函数，使得自定义类型可以直接使用运算符运算。

而第二个函数，实际上是提供了另一种手段，上层可以指定具体类型的比较函数 comp。

无论是代码量，还是执行效率，个人都更喜欢c++一些~

本文相关的测试代码：https://github.com/q191201771/naza/blob/master/playground/p4/p4.go

最后，感谢阅读~