...

Source file src/sort/search.go

Documentation: sort

		 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) }
	 113  

View as plain text