老弟在吗，我怀疑Go标准库中的二分查找有bug！

发表于 | 分类于
| 字数统计: 1.8k

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
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是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
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。

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

1
2
3
4
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包还真提供了：

1
2
3
4
5
6
7
8
9
10
11
12
// - 只需传入整型切片和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包还提供给上层另外一种使用方式：

1
2
3
4
5
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函数声明如下：

1
2
3
4
5
6
7
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

最后，感谢阅读~

本文完，作者yoko，尊重劳动人民成果，转载请注明原文出处： https://pengrl.com/p/20011/

0%