Source file src/pkg/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	// Search calls f(i) only for i in the range [0, n).
    16	//
    17	// A common use of Search is to find the index i for a value x in
    18	// a sorted, indexable data structure such as an array or slice.
    19	// In this case, the argument f, typically a closure, captures the value
    20	// to be searched for, and how the data structure is indexed and
    21	// ordered.
    22	//
    23	// For instance, given a slice data sorted in ascending order,
    24	// the call Search(len(data), func(i int) bool { return data[i] >= 23 })
    25	// returns the smallest index i such that data[i] >= 23.  If the caller
    26	// wants to find whether 23 is in the slice, it must test data[i] == 23
    27	// separately.
    28	//
    29	// Searching data sorted in descending order would use the <=
    30	// operator instead of the >= operator.
    31	//
    32	// To complete the example above, the following code tries to find the value
    33	// x in an integer slice data sorted in ascending order:
    34	//
    35	//	x := 23
    36	//	i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
    37	//	if i < len(data) && data[i] == x {
    38	//		// x is present at data[i]
    39	//	} else {
    40	//		// x is not present in data,
    41	//		// but i is the index where it would be inserted.
    42	//	}
    43	//
    44	// As a more whimsical example, this program guesses your number:
    45	//
    46	//	func GuessingGame() {
    47	//		var s string
    48	//		fmt.Printf("Pick an integer from 0 to 100.\n")
    49	//		answer := sort.Search(100, func(i int) bool {
    50	//			fmt.Printf("Is your number <= %d? ", i)
    51	//			fmt.Scanf("%s", &s)
    52	//			return s != "" && s[0] == 'y'
    53	//		})
    54	//		fmt.Printf("Your number is %d.\n", answer)
    55	//	}
    56	//
    57	func Search(n int, f func(int) bool) int {
    58		// Define f(-1) == false and f(n) == true.
    59		// Invariant: f(i-1) == false, f(j) == true.
    60		i, j := 0, n
    61		for i < j {
    62			h := i + (j-i)/2 // avoid overflow when computing h
    63			// i ≤ h < j
    64			if !f(h) {
    65				i = h + 1 // preserves f(i-1) == false
    66			} else {
    67				j = h // preserves f(j) == true
    68			}
    69		}
    70		// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
    71		return i
    72	}
    73	
    74	// Convenience wrappers for common cases.
    75	
    76	// SearchInts searches for x in a sorted slice of ints and returns the index
    77	// as specified by Search. The slice must be sorted in ascending order.
    78	//
    79	func SearchInts(a []int, x int) int {
    80		return Search(len(a), func(i int) bool { return a[i] >= x })
    81	}
    82	
    83	// SearchFloat64s searches for x in a sorted slice of float64s and returns the index
    84	// as specified by Search. The slice must be sorted in ascending order.
    85	// 
    86	func SearchFloat64s(a []float64, x float64) int {
    87		return Search(len(a), func(i int) bool { return a[i] >= x })
    88	}
    89	
    90	// SearchStrings searches for x slice a sorted slice of strings and returns the index
    91	// as specified by Search. The slice must be sorted in ascending order.
    92	// 
    93	func SearchStrings(a []string, x string) int {
    94		return Search(len(a), func(i int) bool { return a[i] >= x })
    95	}
    96	
    97	// Search returns the result of applying SearchInts to the receiver and x.
    98	func (p IntSlice) Search(x int) int { return SearchInts(p, x) }
    99	
   100	// Search returns the result of applying SearchFloat64s to the receiver and x.
   101	func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
   102	
   103	// Search returns the result of applying SearchStrings to the receiver and x.
   104	func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }