Is there a Go analog of Python's bisect module?

Question

I am looking for an out-of-the-box implementation of Python's bisect module in Go. All that I need is to find a position for inserting an item in a sorted array from the left and from the right.

I know the logic behind the implementation, but I do not want to reinvent the wheel with all of its edge cases.

Answer 1

Yes. sort.Search() is what you want. It takes a length and a comparison function, and returns the first index for which the function returns true. The example in the linked docs includes:

i := sort.Search(len(data), func(i int) bool { return data[i] >= x })

That sets i to the index of the first value >= x (or to len(data) if no items are >= x), so it's like bisect.bisect_left() in Python. Change it to > to get something like bisect_right.

The Python functions will also search through a range within a list; to do something similar, you could search a subslice of your slice, and add its starting offset to the index Search returns if you need an index into the original slice. There are other ways, but that seems simple and readable.

Though this is also true of Python lists, insertion into a sorted slice is O(n), i.e., it averages twice as slow on twice as much data. If either the number of items or the number of inserts is small you might get away the "bad" complexity. If you add a bunch then search a bunch, you could add everything to the end, sort once, then do all your searches, amortizing the cost of the sort.

But for general-purpose sorted collections where inserts, deletes, searches, etc. take logarithmic time regardless of what order you do them in, you may want to turn to tools for ordered collections or databases. There are lots of options, but a couple easy 'starter' ones are github.com/cznic/b and github.com/mattn/go-sqlite3.