去二进制搜索错误

Question

Suppose you have two use cases:

a := [] int {2, 2, 3, 4}
i := sort.Search(len(a), func(pos int) bool { return a[pos] == 2})
fmt.Printf("%v -> %v 
", 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 
", b, j)

Answer for those are:

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

I suppose it must be 1 in both cases, no? Does anyone knows why?

Answer 1

sort.Search() returns the smallest index i in [0, n) at which f(i) is true.

Since slice indices are 0-based, you should expect a return of 0 for the first and 1 for the second. It (seemingly) works for the second.

Quoting from the doc:

...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.

Your function does not meet the criteria sort.Search() expects. Your function is not to tell if the element at the specified index is the one you're looking for, but rather to tell:

• if the element at the requested index is equal to or is greater than (return true)
• or if the element at the specified index is less than the searched one (return false).

(A binary search could not be carried out if you would only tell when they are equal but not when they are greater or less.)

So simply use >= comparison instead of ==. Correct usage:

a := []int{2, 2, 3, 4}
i := sort.Search(len(a), func(pos int) bool { return a[pos] >= 2 })
fmt.Printf("%v -> %v 
", 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 
", b, j)

Output (try it on the <kbd>Go Playground</kbd>):

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

Note: also from the doc:

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.

Easier alternative: sort.SearchInts()

If you want to search for an int value in an int slice ([]int), simply use sort.SearchInts():

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

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

Output (try it on the <kbd>Go Playground</kbd>):

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