Ming
0%

sort.Search

Posted on Edited on In

二分查找

Go的sort包提供了一个二分查找的方法：sort.Search：

1
func Search(n int, f func(int) bool) int

最初第一次看到这个函数的参数和返回值，有点疑惑，在我的印象中，二分查找是在一个有序数组中查找某一个特定的元素，返回其在数组中的位置。但接受一个整型的n和一个返回布尔值的闭包函数是为哪般？

看了文档，用了几次之后，越来越发觉这个函数设计的很妙。

有序不一定非得是 [1, 2, 3, 4] ，可以再放宽条件：存在一个分界点（数组中的某个元素，假设下标为i），分界点的左边有同一种特质，分界点及其右边有另一种特质，对应到这个函数，则是：f(0 ~ i-1) == false，f(i ~ n) == true，其中n是数组的大小。

接着就可以用折半（二分）查找的方式，找到该分界点。

可以用该函数查找有序数组中的某个元素位置：

1
2
3
4
5
nums := []int{1, 2, 3, 4, 5}
x := sort.Search(4, func(i int) bool {
	return nums[i] >= 4
})
fmt.Println(x) // x = 3

更为重要的是，可以查找“那个”分界点。比如这道算法题：

1482. 制作 m 束花所需的最少天数

拥有更强的泛化能力，但sort.Search的实现，却和二分查找如出一辙：

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
}

值得注意的是，假如没找到那个分界点，会返回0，而不是-1 。

Search uses binary search to find and return the smallest index i in [0, n) at which f(i) is true, 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. (Note that the “not found” return value is not -1 as in, for instance, strings.Index.) Search calls f(i) only for i in the range [0, n).
A common use of Search is to find the index i for a value x in a sorted, indexable data structure such as an array or slice. In this case, the argument f, typically a closure, captures the value to be searched for, and how the data structure is indexed and ordered.
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.
Searching data sorted in descending order would use the <= operator instead of the >= operator.
To complete the example above, the following code tries to find the value x in an integer slice data sorted in ascending order:

1
2
3
4
5
6
7
8
x := 23
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
if i < len(data) && data[i] == x {
 // x is present at data[i]
} else {
 // x is not present in data,
 // but i is the index where it would be inserted.
}

As a more whimsical example, this program guesses your number:

1
2
3
4
5
6
7
8
9
10
func GuessingGame() {
 var s string
 fmt.Printf("Pick an integer from 0 to 100.\n")
 answer := sort.Search(100, func(i int) bool {
  fmt.Printf("Is your number <= %d? ", i)
  fmt.Scanf("%s", &s)
  return s != "" && s[0] == 'y'
 })
 fmt.Printf("Your number is %d.\n", answer)
}