Is there an analogue analogue of the Bisect Python module?
I'm looking for a ready-made version of the Python bisect
module in Go. All I need is to find the position to insert the element into the sorted array from left and from right .
I know the implementation logic, but I don't want to reinvent the wheel with all of its edge cases.
source to share
Yes. sort.Search()
- Is this what you want. It takes a length and comparison function and returns the first index for which the function returns true. Example in linked docs includes:
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
This sets i
the index to the first >=
x value (or len(data)
if there are no >=
x elements ), so it likes it bisect.bisect_left()
in Python. Change it to >
to get something like bisect_right
.
Python functions will also search for a range in the list; to do something like this, you can search for a subsection of your slice and add its starting offset to the index Search
if you need the index to the original slice. There are other ways as well, but it seems simple and readable.
While this is true for Python lists too, inserting into a sorted slice is O (n), meaning it is twice as slow as twice the data. It's still fine for many purposes (many times you have a small list or multiple attachments), but of course you can't scale infinitely that way. If you're inserting a ton of items, like a sizable chunk of the list size, you can add them all and then sort. For general sorted collections with log-time insertions, deletions, etc. There is always, for example, github.com/cznic/b
or any amount of data, y things.
source to share