golang search 代码
文件路径：/src/sort/search.go
/ Copyright 2010 The Go Authors. All rights reserved.
/ Use of this source code is governed by a BSD-style
/ license that can be found in the LICENSE file.
/ This file implements binary search.
package sort
/ 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:
/
/ 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:
/
/ 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)
/ }
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
}
/ Find uses binary search to find and return the smallest index i in [0, n)
/ at which cmp(i) <= 0. If there is no such index i, Find returns i = n.
/ The found result is true if i < n and cmp(i) == 0.
/ Find calls cmp(i) only for i in the range [0, n).
/
/ To permit binary search, Find requires that cmp(i) > 0 for a leading
/ prefix of the range, cmp(i) == 0 in the middle, and cmp(i) < 0 for
/ the final suffix of the range. (Each subrange could be empty.)
/ The usual way to establish this condition is to interpret cmp(i)
/ as a comparison of a desired target value t against entry i in an
/ underlying indexed data structure x, returning <0, 0, and >0
/ when t < x[i], t == x[i], and t > x[i], respectively.
/
/ For example, to look for a particular string in a sorted, random-access
/ list of strings:
/
/ i, found := sort.Find(x.Len(), func(i int) int {
/ return strings.Compare(target, x.At(i))
/ })
/ if found {
/ fmt.Printf("found %s at entry %d\n", target, i)
/ } else {
/ fmt.Printf("%s not found, would insert at %d", target, i)
/ }
func Find(n int, cmp func(int) int) (i int, found bool) {
/ The invariants here are similar to the ones in Search.
/ Define cmp(-1) > 0 and cmp(n) <= 0
/ Invariant: cmp(i-1) > 0, cmp(j) <= 0
i, j := 0, n
for i < j {
h := int(uint(i+j) >> 1) / avoid overflow when computing h
/ i ≤ h < j
if cmp(h) > 0 {
i = h + 1 / preserves cmp(i-1) > 0
} else {
j = h / preserves cmp(j) <= 0
}
}
/ i == j, cmp(i-1) > 0 and cmp(j) <= 0
return i, i < n && cmp(i) == 0
}
/ Convenience wrappers for common cases.
/ SearchInts searches for x in a sorted slice of ints and returns the index
/ as specified by Search. The return value is the index to insert x if x is
/ not present (it could be len(a)).
/ The slice must be sorted in ascending order.
func SearchInts(a []int, x int) int {
return Search(len(a), func(i int) bool { return a[i] >= x })
}
/ SearchFloat64s searches for x in a sorted slice of float64s and returns the index
/ as specified by Search. The return value is the index to insert x if x is not
/ present (it could be len(a)).
/ The slice must be sorted in ascending order.
func SearchFloat64s(a []float64, x float64) int {
return Search(len(a), func(i int) bool { return a[i] >= x })
}
/ SearchStrings searches for x in a sorted slice of strings and returns the index
/ as specified by Search. The return value is the index to insert x if x is not
/ present (it could be len(a)).
/ The slice must be sorted in ascending order.
func SearchStrings(a []string, x string) int {
return Search(len(a), func(i int) bool { return a[i] >= x })
}
/ Search returns the result of applying SearchInts to the receiver and x.
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }
/ Search returns the result of applying SearchFloat64s to the receiver and x.
func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
/ Search returns the result of applying SearchStrings to the receiver and x.
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }