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
7package 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//	}
58func 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//	}
99func 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.
123func 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.
131func 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.
139func SearchStrings(a []string, x string) int {
140	return Search(len(a), func(i int) bool { return a[i] >= x })
141}
142
143// Search returns the result of applying [SearchInts] to the receiver and x.
144func (p IntSlice) Search(x int) int { return SearchInts(p, x) }
145
146// Search returns the result of applying [SearchFloat64s] to the receiver and x.
147func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
148
149// Search returns the result of applying [SearchStrings] to the receiver and x.
150func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }
151