libgo/go/sort/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 //
  59 func Search(n int, f func(int) bool) int {
  60         // Define f(-1) == false and f(n) == true.
  61         // Invariant: f(i-1) == false, f(j) == true.
  62         i, j := 0, n
  63         for i < j {
  64                 h := int(uint(i+j) >> 1) // avoid overflow when computing h
  65                 // i ≤ h < j
  66                 if !f(h) {
  67                         i = h + 1 // preserves f(i-1) == false
  68                 } else {
  69                         j = h // preserves f(j) == true
  70                 }
  71         }
  72         // i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
  73         return i
  74 }
  75
  76 // Convenience wrappers for common cases.
  77
  78 // SearchInts searches for x in a sorted slice of ints and returns the index
  79 // as specified by Search. The return value is the index to insert x if x is
  80 // not present (it could be len(a)).
  81 // The slice must be sorted in ascending order.
  82 //
  83 func SearchInts(a []int, x int) int {
  84         return Search(len(a), func(i int) bool { return a[i] >= x })
  85 }
  86
  87 // SearchFloat64s searches for x in a sorted slice of float64s and returns the index
  88 // as specified by Search. The return value is the index to insert x if x is not
  89 // present (it could be len(a)).
  90 // The slice must be sorted in ascending order.
  91 //
  92 func SearchFloat64s(a []float64, x float64) int {
  93         return Search(len(a), func(i int) bool { return a[i] >= x })
  94 }
  95
  96 // SearchStrings searches for x in a sorted slice of strings and returns the index
  97 // as specified by Search. The return value is the index to insert x if x is not
  98 // present (it could be len(a)).
  99 // The slice must be sorted in ascending order.
 100 //
 101 func SearchStrings(a []string, x string) int {
 102         return Search(len(a), func(i int) bool { return a[i] >= x })
 103 }
 104
 105 // Search returns the result of applying SearchInts to the receiver and x.
 106 func (p IntSlice) Search(x int) int { return SearchInts(p, x) }
 107
 108 // Search returns the result of applying SearchFloat64s to the receiver and x.
 109 func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
 110
 111 // Search returns the result of applying SearchStrings to the receiver and x.
 112 func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }