Bisect, is it possible to work with descending sorted lists?
Probably the easiest thing is to borrow the code from the library and make your own version
def reverse_insort(a, x, lo=0, hi=None):
"""Insert item x in list a, and keep it reverse-sorted assuming a
is reverse-sorted.
If x is already in a, insert it to the right of the rightmost x.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if x > a[mid]: hi = mid
else: lo = mid+1
a.insert(lo, x)
In Python 3.10, insort
gain a key
parameter, from the documentation:
key specifies a key function of one argument that is used to extract a comparison key from each input element. The default value is None (compare the elements directly).
So, to insert in a descending sorted list do:
import bisect
x = [1.0,2.0,3.0,4.0]
x.reverse()
bisect.insort(x, 2.5, key=lambda x: -1 * x)
print(x)
Output
[4.0, 3.0, 2.5, 2.0, 1.0]
It is better to stick to the built-in python library, per @reve_etrange's comment unless you are working on a platform that allows you to use alternative C-extension implementations which might be faster. The following would leverage the built-in Python bisect module.
ASC = 'asc'
DESC = 'desc'
def bisect_left(l, e, lo=None, hi=None, order=ASC):
"""Find first index, starting from left, to insert e."""
lo = lo or 0
hi = hi or len(l)
if order not in (ASC, DESC):
raise ValueError('order must either be asc or desc.')
if order == ASC:
return bisect.bisect_left(l, e, lo, hi)
return len(l) - bisect.bisect_right(l[::-1], e, lo, hi)
def bisect_right(l, e, lo=None, hi=None, order=ASC):
"""Find first index, starting from right, to insert e."""
lo = lo or 0
hi = hi or len(l)
if order not in (ASC, DESC):
raise ValueError('order must either be asc or desc.')
if order == ASC:
return bisect.bisect_right(l, e, lo, hi)
return len(l) - bisect.bisect_left(l[::-1], e, lo, hi)