search - 去二分查找错误

Question

假设您有两个用例:

a := [] int {2, 2, 3, 4}
i := sort.Search(len(a), func(pos int) bool { return a[pos] == 2})
fmt.Printf("%v -> %v \n", a, i)

b := [] int {1, 2, 2, 3, 4}
j := sort.Search(len(b), func(pos int) bool { return b[pos] == 2})
fmt.Printf("%v -> %v \n", b, j)

答案是:

[2 2 3 4] -> 4
[1 2 2 3 4] -> 1

我想在这两种情况下它都必须是 1，不是吗？有谁知道为什么吗？

Answer 1

sort.Search()返回 [0, n) 中 f(i) 为 true 的最小索引 i。

由于 slice 索引是从 0 开始的，因此您应该期望第一个返回 0，第二个返回 1。它(似乎)适用于第二个。

引用文档:

...assuming that on the range [0, n), f(i) == true implies f(i+1) == true. That is, Search requires that f is false for some (possibly empty) prefix of the input range [0, n) and then true for the (possibly empty) remainder; Search returns the first true index. If there is no such index, Search returns n.

您的函数不符合 sort.Search() 期望的条件。您的功能不是判断指定索引处的元素是否是您要查找的元素，而是告诉:

• 如果请求索引处的元素等于或大于(返回true)
• 或者如果指定索引处的元素小于搜索到的元素(返回false)。

(如果您只判断它们何时相等而不判断它们何时大于或小于，则无法进行二分查找。)

所以简单地使用>=比较而不是==。正确用法:

a := []int{2, 2, 3, 4}
i := sort.Search(len(a), func(pos int) bool { return a[pos] >= 2 })
fmt.Printf("%v -> %v \n", a, i)

b := []int{1, 2, 2, 3, 4}
j := sort.Search(len(b), func(pos int) bool { return b[pos] >= 2 })
fmt.Printf("%v -> %v \n", b, j)

输出(在 Go Playground 上尝试):

[2 2 3 4] -> 0 
[1 2 2 3 4] -> 1 

注意:同样来自文档:

For instance, given a slice data sorted in ascending order, the call

Search(len(data), func(i int) bool { return data[i] >= 23 })

returns the smallest index i such that data[i] >= 23. If the caller wants to find whether 23 is in the slice, it must test data[i] == 23 separately.

更简单的选择:sort.SearchInts()

如果您想在 int slice ([]int) 中搜索 int 值，只需使用 sort.SearchInts() :

a := []int{2, 2, 3, 4}
i := sort.SearchInts(a, 2)
fmt.Printf("%v -> %v \n", a, i)

b := []int{1, 2, 2, 3, 4}
j := sort.SearchInts(b, 2)
fmt.Printf("%v -> %v \n", b, j)

输出(在 Go Playground 上尝试):

[2 2 3 4] -> 0 
[1 2 2 3 4] -> 1