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) }
Define f(-1) == false and f(n) == true. Invariant: f(i-1) == false, f(j) == true.
	,  := 0, 
	for  <  {
i ≤ h < j
		if !() {
			 =  + 1 // preserves f(i-1) == false
		} else {
			 =  // preserves f(j) == true
		}
i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
	return 
}
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 ( []int,  int) int {
	return Search(len(), func( int) bool { return [] >=  })
}
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 ( []float64,  float64) int {
	return Search(len(), func( int) bool { return [] >=  })
}
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 ( []string,  string) int {
	return Search(len(), func( int) bool { return [] >=  })
}
Search returns the result of applying SearchInts to the receiver and x.
func ( IntSlice) ( int) int { return SearchInts(, ) }
Search returns the result of applying SearchFloat64s to the receiver and x.
func ( Float64Slice) ( float64) int { return SearchFloat64s(, ) }
Search returns the result of applying SearchStrings to the receiver and x.