diff options
Diffstat (limited to 'src/sort/search.go')
-rw-r--r-- | src/sort/search.go | 112 |
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) } |