pythonbinary-searchsortedcontainers

How to use binary search on an existing SortedList with a key function?

I would like to use binary search on a SortedList with a key function, e.g. similarly to bisect_right() in the bisect module. However, SortedList.bisect_right() only supports searching by value. How to make it work with a key function?

Solution

  • If you have a SortedList already and it's sorted by the given key, you can use bisect.bisect_right on that, e.g.:

    bisect.bisect_right(sorted_list, value, key=keyfunc)

    If you need to search repeatedly, it would be more efficient to create a SortedKeyList and use its bisect_key_right() method. The extra efficiency comes from not indexing the sorted list during a binary search, as that itself is a O(log(n)) operation.