← Back to branch summary

~ubuntu-branches/ubuntu/vivid/golang/vivid

« back to all changes in this revision

Viewing changes to src/pkg/sort/search.go

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2013-08-20 14:06:23 UTC
  • mfrom: (14.1.23 saucy-proposed)
  • Revision ID: package-import@ubuntu.com-20130820140623-b414jfxi3m0qkmrq
Tags: 2:1.1.2-2ubuntu1
https://launchpad.net/bugs/1211749
https://launchpad.net/bugs/1202027
* Merge from Debian unstable (LP: #1211749, #1202027). Remaining changes:
  - 016-armhf-elf-header.patch: Use correct ELF header for armhf binaries.
  - d/control,control.cross: Update Breaks/Replaces for Ubuntu
    versions to ensure smooth upgrades, regenerate control file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/sort/search.go
7
7
package sort
8
8
 
9
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), 
 
10
// in [0, n) at which f(i) is true, assuming that on the range [0, n),
11
11
// f(i) == true implies f(i+1) == true.  That is, Search requires that
12
12
// f is false for some (possibly empty) prefix of the input range [0, n)
13
13
// and then true for the (possibly empty) remainder; Search returns
14
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).
15
17
// Search calls f(i) only for i in the range [0, n).
16
18
//
17
19
// A common use of Search is to find the index i for a value x in
74
76
// Convenience wrappers for common cases.
75
77
 
76
78
// 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.
 
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.
78
82
//
79
83
func SearchInts(a []int, x int) int {
80
84
        return Search(len(a), func(i int) bool { return a[i] >= x })
81
85
}
82
86
 
83
87
// 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
 
// 
 
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
//
86
92
func SearchFloat64s(a []float64, x float64) int {
87
93
        return Search(len(a), func(i int) bool { return a[i] >= x })
88
94
}
89
95
 
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
 
// 
 
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
//
93
101
func SearchStrings(a []string, x string) int {
94
102
        return Search(len(a), func(i int) bool { return a[i] >= x })
95
103
}