Best way of implementing generic binary search?

[Slawomir Pryczek]

Hi Guys, is it possible to implement generic, efficient binary search using generics or interfaces. So i'll have some index, and data inside single struct and then could just define a comparison function between 2 variables of same type index which will return bool.

Will have 20-30 million datapoints

type abc struct {
index  uint32
data1 []byte
data2 []string
}
type bcd struct {
index  [4]byte
data1 []byte
data2 []string
}

a = []abc{...}
b = []bcd{...}
find(a, 217621)

find(b, [4]byte{1,2,54,11})

Currently i have this, which is probably incorrect:

type comparable[TC any] interface {
compare(TC, TC) bool
}

func bin[T comparable](data []T, find T) int {
}

Is that even possible to do efficiently or i should just go with writing separated code for each struct type ?

[Martin Schnabel]

Hi, there is an experimental package golang.org/x/exp/slices which has a
generic binary search. I have not much to add but hope it helps.

https://pkg.go.dev/golang.org/x/exp/slices
https://cs.opensource.google/go/x/exp/+/79cabaa2:slices/sort.go;l=64

> --
> 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
> <mailto:golang-nuts...@googlegroups.com>.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/golang-nuts/a7e769c3-70a7-4aa6-96a5-453a55db3e60n%40googlegroups.com
> <https://groups.google.com/d/msgid/golang-nuts/a7e769c3-70a7-4aa6-96a5-453a55db3e60n%40googlegroups.com?utm_medium=email&utm_source=footer>.

[Brian Candler]

You don't need a compare method on your type.  You can just pass a func(T, T) bool to your search function.

In fact, the standard library already has this, except implemented in terms of slice indexes only, rather than a slice of generic type.

https://pkg.go.dev/sort#Search

You could always make a generic Search[T] as a counterpart to SearchFloat64s, SearchInts and SearchStrings.  Since the source of those existing functions is simple, this is left as an exercise for the reader :-)

https://cs.opensource.google/go/go/+/refs/tags/go1.18.4:src/sort/search.go;l=76-103

[Slawomir Pryczek]

Thanks everyone, was able to make this working by passing a function with same type.