golang-sort-searchint-behavior

Posted on Comments:

// 這篇還沒寫完

sort.Ints, sort.Strings, sort.Float64s
sort.SearchInts
sort.SearchStrings
sort.SearchFloat64s

背後是 Binary Search。

int(uint(i+j) >> 1

n == len(slice), f 有點類似 C++ STL std::find_if 的 Predicate。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
}
1
2
3
func SearchInts(a []int, x int) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}