Subversion Repositories openrisc

// 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.

// 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 {

        // Define f(-1) == false and f(n) == true.

        // Invariant: f(i-1) == false, f(j) == true.

        i, j := 0, n

        for i < j {

                h := i + (j-i)/2 // 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

}

// Convenience wrappers for common cases.

// SearchInts searches for x in a sorted slice of ints and returns the index

// as specified by Search. 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 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 slice a sorted slice of strings and returns the index

// as specified by Search. 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) }