summaryrefslogtreecommitdiffstats
path: root/src/sort/search.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/sort/search.go')
-rw-r--r--src/sort/search.go112
1 files changed, 112 insertions, 0 deletions
diff --git a/src/sort/search.go b/src/sort/search.go
new file mode 100644
index 0000000..fcff0f9
--- /dev/null
+++ b/src/sort/search.go
@@ -0,0 +1,112 @@
+// 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
+}
+
+// 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) }