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