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 func Search(n int, f func(int) bool) int {
59 // Define f(-1) == false and f(n) == true.
60 // Invariant: f(i-1) == false, f(j) == true.
61 i, j := 0, n
62 for i < j {
63 h := int(uint(i+j) >> 1) // avoid overflow when computing h
64 // i ≤ h < j
65 if !f(h) {
66 i = h + 1 // preserves f(i-1) == false
67 } else {
68 j = h // preserves f(j) == true
69 }
70 }
71 // i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
72 return i
73 }
74 75 // Find uses binary search to find and return the smallest index i in [0, n)
76 // at which cmp(i) <= 0. If there is no such index i, Find returns i = n.
77 // The found result is true if i < n and cmp(i) == 0.
78 // Find calls cmp(i) only for i in the range [0, n).
79 //
80 // To permit binary search, Find requires that cmp(i) > 0 for a leading
81 // prefix of the range, cmp(i) == 0 in the middle, and cmp(i) < 0 for
82 // the final suffix of the range. (Each subrange could be empty.)
83 // The usual way to establish this condition is to interpret cmp(i)
84 // as a comparison of a desired target value t against entry i in an
85 // underlying indexed data structure x, returning <0, 0, and >0
86 // when t < x[i], t == x[i], and t > x[i], respectively.
87 //
88 // For example, to look for a particular string in a sorted, random-access
89 // list of strings:
90 //
91 // i, found := sort.Find(x.Len(), func(i int) int {
92 // return strings.Compare(target, x.At(i))
93 // })
94 // if found {
95 // fmt.Printf("found %s at entry %d\n", target, i)
96 // } else {
97 // fmt.Printf("%s not found, would insert at %d", target, i)
98 // }
99 func Find(n int, cmp func(int) int) (i int, found bool) {
100 // The invariants here are similar to the ones in Search.
101 // Define cmp(-1) > 0 and cmp(n) <= 0
102 // Invariant: cmp(i-1) > 0, cmp(j) <= 0
103 i, j := 0, n
104 for i < j {
105 h := int(uint(i+j) >> 1) // avoid overflow when computing h
106 // i ≤ h < j
107 if cmp(h) > 0 {
108 i = h + 1 // preserves cmp(i-1) > 0
109 } else {
110 j = h // preserves cmp(j) <= 0
111 }
112 }
113 // i == j, cmp(i-1) > 0 and cmp(j) <= 0
114 return i, i < n && cmp(i) == 0
115 }
116 117 // Convenience wrappers for common cases.
118 119 // SearchInts searches for x in a sorted slice of ints and returns the index
120 // as specified by [Search]. The return value is the index to insert x if x is
121 // not present (it could be len(a)).
122 // The slice must be sorted in ascending order.
123 func SearchInts(a []int, x int) int {
124 return Search(len(a), func(i int) bool { return a[i] >= x })
125 }
126 127 // SearchFloat64s searches for x in a sorted slice of float64s and returns the index
128 // as specified by [Search]. The return value is the index to insert x if x is not
129 // present (it could be len(a)).
130 // The slice must be sorted in ascending order.
131 func SearchFloat64s(a []float64, x float64) int {
132 return Search(len(a), func(i int) bool { return a[i] >= x })
133 }
134 135 // SearchStrings searches for x in a sorted slice of strings and returns the index
136 // as specified by Search. The return value is the index to insert x if x is not
137 // present (it could be len(a)).
138 // The slice must be sorted in ascending order.
139 func SearchStrings(a [][]byte, x []byte) int {
140 return Search(len(a), func(i int) bool { return []byte(a[i]) >= []byte(x) })
141 }
142 143 // Search returns the result of applying [SearchInts] to the receiver and x.
144 func (p IntSlice) Search(x int) int { return SearchInts(p, x) }
145 146 // Search returns the result of applying [SearchFloat64s] to the receiver and x.
147 func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
148 149 // Search returns the result of applying [SearchStrings] to the receiver and x.
150 func (p StringSlice) Search(x []byte) int { return SearchStrings(p, x) }
151