Ah, my last post had a small mistake. A small modification to upper should
be all you need. The function should use >= instead of >. See below.
upper := sort.Search(len(haystack), func(i int) bool {
return haystack[i].name >= needle.name
})
On Tue, Oct 11, 2022, 7:38 AM K. Alex Mills <k.alex.mi...@gmail.com> wrote:
> 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/CALJzkY9O5F_trJAhp8i8jSdVOb7wf%2Brz06JEHu8GXoQuVPQkVQ%40mail.gmail.com.
