Steve D Steve D - 1 year ago 258
Python Question

python bisect, it is possible to work with descending sorted lists?

How can I use bisect module on lists that are sorted descending?
eg.

import bisect

x = [1.0,2.0,3.0,4.0] # normal, ascending
bisect.insort(x,2.5) # --> x is [1.0, 2.0, 2.5, 3.0, 4.0] ok, works fine for ascending list

# however
x = [1.0,2.0,3.0,4.0]
x.reverse() # --> x is [4.0, 3.0, 2.0, 1.0] descending list
bisect.insort(x,2.5) # --> x is [4.0, 3.0, 2.0, 1.0, 2.5] 2.5 at end, not what I want really


The only methods are insort (insort_right) or insort_left - none of which work for me.
Any suggestions? thank you

Answer Source

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)