````// 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 == 'y'`
`//		})`
`//		fmt.Printf("Your number is %d.\n", answer)`
`//	}`
`func Search(n int, f func(int) bool) int {`
`	// Define f(-1) == false and f(n) == true.`
`	// Invariant: f(i-1) == false, f(j) == true.`
`	i, j := 0, n`
`	for i < j {`
`		h := int(uint(i+j) >> 1) // avoid overflow when computing h`
`		// i ≤ h < j`
`		if !f(h) {`
`			i = h + 1 // preserves f(i-1) == false`
`		} else {`
`			j = h // preserves f(j) == true`
`		}`
`	}`
`	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.`
`	return i`
`}`

`// Find uses binary search to find and return the smallest index i in [0, n)`
`// at which cmp(i) <= 0. If there is no such index i, Find returns i = n.`
`// The found result is true if i < n and cmp(i) == 0.`
`// Find calls cmp(i) only for i in the range [0, n).`
`//`
`// To permit binary search, Find requires that cmp(i) > 0 for a leading`
`// prefix of the range, cmp(i) == 0 in the middle, and cmp(i) < 0 for`
`// the final suffix of the range. (Each subrange could be empty.)`
`// The usual way to establish this condition is to interpret cmp(i)`
`// as a comparison of a desired target value t against entry i in an`
`// underlying indexed data structure x, returning <0, 0, and >0`
`// when t < x[i], t == x[i], and t > x[i], respectively.`
`//`
`// For example, to look for a particular string in a sorted, random-access`
`// list of strings:`
`//`
`//	i, found := sort.Find(x.Len(), func(i int) int {`
`//	    return strings.Compare(target, x.At(i))`
`//	})`
`//	if found {`
`//	    fmt.Printf("found %s at entry %d\n", target, i)`
`//	} else {`
`//	    fmt.Printf("%s not found, would insert at %d", target, i)`
`//	}`
`func Find(n int, cmp func(int) int) (i int, found bool) {`
`	// The invariants here are similar to the ones in Search.`
`	// Define cmp(-1) > 0 and cmp(n) <= 0`
`	// Invariant: cmp(i-1) > 0, cmp(j) <= 0`
`	i, j := 0, n`
`	for i < j {`
`		h := int(uint(i+j) >> 1) // avoid overflow when computing h`
`		// i ≤ h < j`
`		if cmp(h) > 0 {`
`			i = h + 1 // preserves cmp(i-1) > 0`
`		} else {`
`			j = h // preserves cmp(j) <= 0`
`		}`
`	}`
`	// i == j, cmp(i-1) > 0 and cmp(j) <= 0`
`	return i, i < n && cmp(i) == 0`
`}`

`// 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 SearchInts(a []int, x int) int {`
`	return Search(len(a), func(i int) bool { return a[i] >= x })`
`}`

`// 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 SearchFloat64s(a []float64, x float64) int {`
`	return Search(len(a), func(i int) bool { return a[i] >= x })`
`}`

`// 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 SearchStrings(a []string, x string) int {`
`	return Search(len(a), func(i int) bool { return a[i] >= x })`
`}`

`// Search returns the result of applying SearchInts to the receiver and x.`
`func (p IntSlice) Search(x int) int { return SearchInts(p, x) }`

`// Search returns the result of applying SearchFloat64s to the receiver and x.`
`func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }`

`// Search returns the result of applying SearchStrings to the receiver and x.`
`func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }`
```