1 // Copyright 2010 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 // This file implements binary search. 6 7 package sort 8 9 // Search uses binary search to find and return the smallest index i 10 // in [0, n) at which f(i) is true, assuming that on the range [0, n), 11 // f(i) == true implies f(i+1) == true. That is, Search requires that 12 // f is false for some (possibly empty) prefix of the input range [0, n) 13 // and then true for the (possibly empty) remainder; Search returns 14 // the first true index. If there is no such index, Search returns n. 15 // (Note that the "not found" return value is not -1 as in, for instance, 16 // strings.Index.) 17 // Search calls f(i) only for i in the range [0, n). 18 // 19 // A common use of Search is to find the index i for a value x in 20 // a sorted, indexable data structure such as an array or slice. 21 // In this case, the argument f, typically a closure, captures the value 22 // to be searched for, and how the data structure is indexed and 23 // ordered. 24 // 25 // For instance, given a slice data sorted in ascending order, 26 // the call Search(len(data), func(i int) bool { return data[i] >= 23 }) 27 // returns the smallest index i such that data[i] >= 23. If the caller 28 // wants to find whether 23 is in the slice, it must test data[i] == 23 29 // separately. 30 // 31 // Searching data sorted in descending order would use the <= 32 // operator instead of the >= operator. 33 // 34 // To complete the example above, the following code tries to find the value 35 // x in an integer slice data sorted in ascending order: 36 // 37 // x := 23 38 // i := sort.Search(len(data), func(i int) bool { return data[i] >= x }) 39 // if i < len(data) && data[i] == x { 40 // // x is present at data[i] 41 // } else { 42 // // x is not present in data, 43 // // but i is the index where it would be inserted. 44 // } 45 // 46 // As a more whimsical example, this program guesses your number: 47 // 48 // func GuessingGame() { 49 // var s string 50 // fmt.Printf("Pick an integer from 0 to 100.\n") 51 // answer := sort.Search(100, func(i int) bool { 52 // fmt.Printf("Is your number <= %d? ", i) 53 // fmt.Scanf("%s", &s) 54 // return s != "" && s[0] == 'y' 55 // }) 56 // fmt.Printf("Your number is %d.\n", answer) 57 // } 58 // 59 func Search(n int, f func(int) bool) int { 60 // Define f(-1) == false and f(n) == true. 61 // Invariant: f(i-1) == false, f(j) == true. 62 i, j := 0, n 63 for i < j { 64 h := int(uint(i+j) >> 1) // avoid overflow when computing h 65 // i ≤ h < j 66 if !f(h) { 67 i = h + 1 // preserves f(i-1) == false 68 } else { 69 j = h // preserves f(j) == true 70 } 71 } 72 // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i. 73 return i 74 } 75 76 // Convenience wrappers for common cases. 77 78 // SearchInts searches for x in a sorted slice of ints and returns the index 79 // as specified by Search. The return value is the index to insert x if x is 80 // not present (it could be len(a)). 81 // The slice must be sorted in ascending order. 82 // 83 func SearchInts(a []int, x int) int { 84 return Search(len(a), func(i int) bool { return a[i] >= x }) 85 } 86 87 // SearchFloat64s searches for x in a sorted slice of float64s and returns the index 88 // as specified by Search. The return value is the index to insert x if x is not 89 // present (it could be len(a)). 90 // The slice must be sorted in ascending order. 91 // 92 func SearchFloat64s(a []float64, x float64) int { 93 return Search(len(a), func(i int) bool { return a[i] >= x }) 94 } 95 96 // SearchStrings searches for x in a sorted slice of strings and returns the index 97 // as specified by Search. The return value is the index to insert x if x is not 98 // present (it could be len(a)). 99 // The slice must be sorted in ascending order. 100 // 101 func SearchStrings(a []string, x string) int { 102 return Search(len(a), func(i int) bool { return a[i] >= x }) 103 } 104 105 // Search returns the result of applying SearchInts to the receiver and x. 106 func (p IntSlice) Search(x int) int { return SearchInts(p, x) } 107 108 // Search returns the result of applying SearchFloat64s to the receiver and x. 109 func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) } 110 111 // Search returns the result of applying SearchStrings to the receiver and x. 112 func (p StringSlice) Search(x string) int { return SearchStrings(p, x) } 113