diff options
Diffstat (limited to 'src/pkg/sort/search.go')
| -rw-r--r-- | src/pkg/sort/search.go | 112 |
1 files changed, 0 insertions, 112 deletions
diff --git a/src/pkg/sort/search.go b/src/pkg/sort/search.go deleted file mode 100644 index 8a2c1c33b..000000000 --- a/src/pkg/sort/search.go +++ /dev/null @@ -1,112 +0,0 @@ -// 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 := i + (j-i)/2 // 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) } |