sort.Search runs binary search. It's only guaranteed to work when you
provide it with a function which is monotonic -- true at index i implies
true at all indices greater than i.
Your loop style search does not provide a monotonic function, whereas your
"upper" function is monotonic. However, since "lower" is also not monotonic
I'd question whether the first approach would continue to work on larger
arrays. When testing binary search algorithms, it's important to use arrays
of many varying sizes, since the edge cases often don't appear on smaller
length lists.
In any case, on a sorted list, "upper" should be the only function you need
to determine whether the needle can be found in the list. sort.Search
guarantees that the index it returns is the first index where the monotonic
function changes its value. If the needle you're looking for is in the
haystack, the value at that index will be the needle itself.
On Tue, Oct 11, 2022, 7:22 AM 'ljh' via golang-nuts <
golang-nuts@googlegroups.com> wrote:
> Hi community,
>
> I used sort.Search on a sorted slice in below code started at Line 36, and
> it worked.
>
> I also tried to call sort.Search in a loop, started at Line 53. It does
> not seem to work. How can I correct the loop version?
>
> Thanks
>
> ---
>
> package main
>
> import (
> "log"
> "sort"
> )
>
> type T struct {
> name string
> }
>
> func main() {
> log.SetFlags(log.LstdFlags | log.Llongfile)
>
> haystack := []T{
> // {name: "apple", },
> {name: "compote", }, //dup
> {name: "orange", },
> {name: "compote", }, //dup
> }
>
> sort.Slice(haystack, func(i, j int) bool {
> if haystack[i].name < haystack[j].name {
> return true
> } else {
> return false
> }
> })
>
> for _, t := range haystack {
> log.Println("sorted", t)
> }
>
> needle := T{name: "compote"}
>
> // Style 1: ok, lower upper bounds style // Line 36
> /*
> lower := sort.Search(len(haystack), func(i int) bool {
> return haystack[i].name == needle.name
> })
>
> upper := sort.Search(len(haystack), func(i int) bool {
> return haystack[i].name > needle.name
> })
>
> if lower != len(haystack) {
> for i := lower; i != upper; i++ {
> log.Println("found", i, haystack[i])
> }
> }
> */
>
> // Style 2: error, loop style // Line 53
> for index := 0; index < len(haystack); index++ {
> ret := sort.Search(len(haystack[index:]), func(i int) bool {
> return haystack[index:][i].name == needle.name })
>
> log.Println(index, ret)
>
> if ret < len(haystack) {
> index += ret
> log.Println("found", index, haystack[index])
> }
> }
> }
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts+unsubscr...@googlegroups.com.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/golang-nuts/tencent_659665C8263F2DF81643C2B86412244F3105%40qq.com
> <https://groups.google.com/d/msgid/golang-nuts/tencent_659665C8263F2DF81643C2B86412244F3105%40qq.com?utm_medium=email&utm_source=footer>
> .
>
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to golang-nuts+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/CALJzkY_JSC9pGUTuaXdzf1Wayq8%2BQUjpq2dT%3DqsQKhCcy1Sbgg%40mail.gmail.com.
