// 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) // } func Search(n int, f func(int) bool) int { … } // 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) { … } // 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 { … } // 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 { … } // 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 { … } // Search returns the result of applying [SearchInts] to the receiver and x. func (p IntSlice) Search(x int) int { … } // Search returns the result of applying [SearchFloat64s] to the receiver and x. func (p Float64Slice) Search(x float64) int { … } // Search returns the result of applying [SearchStrings] to the receiver and x. func (p StringSlice) Search(x string) int { … }
Codebase Browser
go