...

# Source file src/pkg/sort/search.go

```     1	// Copyright 2010 The Go Authors. All rights reserved.
2	// Use of this source code is governed by a BSD-style
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	//		})
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 := i + (j-i)/2 // 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
```

View as plain text