search.go

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