How to call sort.Search in a loop
96 views
Skip to first unread message
ljh
Oct 11, 2022, 8:22:29 AM10/11/22
to golang-nuts
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])
}
}
}
Brian Candler
Oct 11, 2022, 8:28:20 AM10/11/22
to golang-nuts
sort.Search is a binary chop, and needs an ordering condition, >= or <=. If you use == then it cannot work.
In addition you're getting a panic here:
if ret < len(haystack) {
index += ret
log.Println("found", index, haystack[index])
}
index += ret
log.Println("found", index, haystack[index])
}
by letting index increment past the end of the slice.
K. Alex Mills
Oct 11, 2022, 8:39:19 AM10/11/22
to ljh, golang-nuts
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.
--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/tencent_659665C8263F2DF81643C2B86412244F3105%40qq.com.
K. Alex Mills
Oct 11, 2022, 9:00:40 AM10/11/22
to ljh, golang-nuts
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
})
ljh
Oct 11, 2022, 1:28:28 PM10/11/22
to K. Alex Mills, golang-nuts
Hi community,
I improved my binary search example with both sort.Search and sort.Find.
Please correct me if I got new wrongs with new example.
1.
My original question was if there are duplicate entries in sorted slice.
After I located the first dup, how can I go to the rest of them without loop.
I ever thought using loop was ugly, so I tried to avoid loop.
But I think loop is ok. because dups are adjacent on sorted slice.
2.
How can I use tuple style comparison found in other languages, like:
struct can be used for == only, not for <, >
3.
I think my conditions covered all the cases, but I need an extra trailing return ?
Whats the right way to do it?
if a < b {
return -1
} else if a == b {
return 0
} else if a > b {
return 1
}
return -999 // an extra return
Thanks
//---
//sort.Search example
func sortSearch() {
haystack := []T{
{"aaa", 111},
{"bbb", 222}, //dup
{"bbb", 222}, //dup
{"ccc", 333},
}
needle := T{"bbb", 222}
index := sort.Search(len(haystack), func(i int) bool {
//asc >=
//desc <=
if haystack[i].name >= needle.name ||
haystack[i].name == needle.name &&
haystack[i].num >= needle.num {
return true;
}
return false
})
log.Println(index)
for i := index; i < len(haystack); i++ {
if haystack[i] == needle {
log.Println(i, haystack[i])
} else {
break
}
}
}
//sort.Find example
func sortFind() {
log.SetFlags(log.LstdFlags | log.Llongfile)
haystack := []T{
{"aaa", 111},
{"bbb", 222}, //dup
{"bbb", 222}, //dup
{"ccc", 333},
}
needle := T{"bbb", 222}
i, found := sort.Find(len(haystack), func(i int) int {
//asc -1 0 1
//desc 1 0 -1
if needle.name < haystack[i].name ||
needle.name == haystack[i].name &&
needle.num < haystack[i].num {
return -1
} else
if needle == haystack[i] {
return 0
} else
if needle.name > haystack[i].name ||
needle.name == haystack[i].name &&
needle.num > haystack[i].num {
return 1
}
return 9 // do i have to add this line // Line 66
})
log.Println(found, i)
for i := i; found && i != len(haystack); i++ {
if haystack[i] == needle {
log.Println(i, haystack[i])
} else {
break
}
}
}
Brian Candler
Oct 11, 2022, 3:46:59 PM10/11/22
to golang-nuts
Can you do your code in https://go.dev/play/ and link to it? It makes it much easier to work with. Your original example was complete and runnable, but this one is missing imports and main() function and the like.
You can simplify your loop which prints the matching elements to just this:
You can simplify your loop which prints the matching elements to just this:
for ; index < len(haystack) && haystack[index] == needle; index++ {
log.Println(index, haystack[index])
}
log.Println(index, haystack[index])
}
(Since index is the first position which is *greater than or equal* to the desired key, you always have to test for a match in case it wasn't found at all)
The comparison function in sortSearch looks fine to me. It could simplify to
return haystack[i].name >= needle.name || (haystack[i].name == needle.name &&
haystack[i].num >= needle.num)
haystack[i].num >= needle.num)
The extra 'return' in sortFind is required because Go can't easily prove that all possible cases are covered by those if clauses. You won't need the return if all branches definitely end the function:
if needle.name < haystack[i].name ||
needle.name == haystack[i].name &&
needle.num < haystack[i].num {
return -1
} else if needle == haystack[i] {
return 0
} else if needle.name > haystack[i].name ||
needle.name == haystack[i].name &&
needle.num > haystack[i].num {
return 1
needle.name == haystack[i].name &&
needle.num < haystack[i].num {
return -1
} else if needle == haystack[i] {
return 0
} else if needle.name > haystack[i].name ||
needle.name == haystack[i].name &&
needle.num > haystack[i].num {
return 1
} else {
panic("This is never called")
}
panic("This is never called")
}
Or you could simplify it to:
if needle.name < haystack[i].name ||
needle.name == haystack[i].name &&
needle.num < haystack[i].num {
return -1
} else if needle == haystack[i] {
return 0
needle.name == haystack[i].name &&
needle.num < haystack[i].num {
return -1
} else if needle == haystack[i] {
return 0
} else {
return 1
}
return 1
}
Reply all
Reply to author
Forward
0 new messages