[go] sort: add examples for lower and upper bound using sort.Search

[Suyash (Gerrit)]

Suyash uploaded a change:
https://go-review.googlesource.com/29333

sort: add examples for lower and upper bound using sort.Search

the lower bound is the position an element would be placed at, in an
ascending total ordering of an array

the upper bound is the first position after the lower bound where the
element cannot be placed

to get the number of occurrences of an element in a sorted array in
logarithmic time, you can do `upper bound - lower bound`

follows: https://golang.org/cl/29131

Change-Id: I8b784374c52f27a704c6d32f41eb10af71c3989e
---
M src/sort/example_search_test.go
1 file changed, 60 insertions(+), 0 deletions(-)



diff --git a/src/sort/example_search_test.go
b/src/sort/example_search_test.go
index 345590c..a347eaa 100644
--- a/src/sort/example_search_test.go
+++ b/src/sort/example_search_test.go
@@ -40,3 +40,63 @@
// Output:
// found 6 at index 7 in [55 45 36 28 21 15 10 6 3 1]
}
+
+// Lower Bound: the position of the smallest integer greater than or equal
to an element
+func ExampleSearch_lowerBound() {
+ a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
+ x := 5
+
+ lb := sort.Search(len(a), func(i int) bool { return a[i] >= x })
+ if lb < len(a) {
+ fmt.Printf("lower bound for %d at index: %d, value: %d\n", x, lb, a[lb])
+ } else {
+ fmt.Printf("lower bound for value %d doesn't exist\n", x)
+ }
+ // Output:
+ // lower bound for 5 at index: 2, value: 6
+}
+
+// Lower Bound for descending order array: the first number before a
number definitely less than an element
+func ExampleSearch_lowerBound_descendingOrder() {
+ a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
+ x := 6
+
+ lb := sort.Search(len(a), func(i int) bool { return a[i] < x }) - 1
+ if lb >= 0 {
+ fmt.Printf("lower bound for %d at index: %d, value: %d\n", x, lb, a[lb])
+ } else {
+ fmt.Printf("lower bound for value %d doesn't exist\n", x)
+ }
+ // Output:
+ // lower bound for 6 at index: 7, value: 6
+}
+
+// Upper Bound: the position of the smallest integer greater than an
element
+func ExampleSearch_upperBound() {
+ a := []int{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
+ x := 6
+
+ ub := sort.Search(len(a), func(i int) bool { return a[i] > x })
+ if ub < len(a) {
+ fmt.Printf("upper bound for %d at index: %d, value: %d\n", x, ub, a[ub])
+ } else {
+ fmt.Printf("upper bound for value %d doesn't exist\n", x)
+ }
+ // Output:
+ // upper bound for 6 at index: 3, value: 10
+}
+
+// Upper Bound for descending order array: the first number before a
number less than or equal to an element
+func ExampleSearch_upperBound_descendingOrder() {
+ a := []int{55, 45, 36, 28, 21, 15, 10, 6, 3, 1}
+ x := 6
+
+ ub := sort.Search(len(a), func(i int) bool { return a[i] <= x }) - 1
+ if ub >= 0 {
+ fmt.Printf("upper bound for %d at index: %d, value: %d\n", x, ub, a[ub])
+ } else {
+ fmt.Printf("upper bound for value %d doesn't exist\n", 6)
+ }
+ // Output:
+ // upper bound for 6 at index: 6, value: 10
+}

--
https://go-review.googlesource.com/29333

[Suyash (Gerrit)]

Suyash uploaded a new patch set:

https://go-review.googlesource.com/29333

sort: add examples for lower and upper bound using sort.Search

the lower bound is the first position an element would be placed at,

in an ascending total ordering of an array

the upper bound is the first position after the lower bound
where the element cannot be placed

to get the number of occurrences of an element in a sorted array in
logarithmic time, you can do `upper bound - lower bound`

follows: https://golang.org/cl/29131

Change-Id: I8b784374c52f27a704c6d32f41eb10af71c3989e
---
M src/sort/example_search_test.go
1 file changed, 60 insertions(+), 0 deletions(-)

--
https://go-review.googlesource.com/29333

[Suyash (Gerrit)]

Suyash uploaded a new patch set:

https://go-review.googlesource.com/29333

sort: add examples for lower and upper bound using sort.Search

the lower bound is the first position an element would be placed at,

in an ascending total ordering of an array

the upper bound is the first position after the lower bound
where the element cannot be placed

to get the number of occurrences of an element in a sorted array in
logarithmic time, you can do `upper bound - lower bound`

follows: https://golang.org/cl/29131

Change-Id: I8b784374c52f27a704c6d32f41eb10af71c3989e
---
M src/sort/example_search_test.go
1 file changed, 60 insertions(+), 0 deletions(-)

--
https://go-review.googlesource.com/29333

[Russ Cox (Gerrit)]

Russ Cox has posted comments on this change.

sort: add examples for lower and upper bound using sort.Search

Patch Set 3: Code-Review-2

Thanks, but I think I rather not. It's important that the examples do not
overwhelm the code. There are already two reasonable examples for this
function. Even though these may be reasonable as well, I don't think we
want so many.

--
https://go-review.googlesource.com/29333
Gerrit-Reviewer: Russ Cox <r...@golang.org>
Gerrit-HasComments: No

[Suyash (Gerrit)]

Suyash has abandoned this change. (
https://go-review.googlesource.com/29333 )

Change subject: sort: add examples for lower and upper bound using
sort.Search
......................................................................


Abandoned