Bisect, is it possible to work with descending sorted lists?

Question

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

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.

Answer 1

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)

Answer 2

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]

Answer 3

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)

Answer 4

Slightly updated bisect library code:

def reverse_bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted in descending order.

    The return value i is such that all e in a[:i] have e >= x, and all e in
    a[i:] have e < x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.

    Essentially, the function returns number of elements in a which are >= than x.
    >>> a = [8, 6, 5, 4, 2]
    >>> reverse_bisect_right(a, 5)
    3
    >>> a[:reverse_bisect_right(a, 5)]
    [8, 6, 5]
    """
    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
    return lo

Answer 5

From the documentation:

Unlike the sorted() function, it does not make sense for the bisect() functions to have key or reversed arguments because that would lead to an inefficent design (successive calls to bisect functions would not “remember” all of the previous key lookups).

Therefore, if you have a list with inverse order, then you are out of luck.

The main usecase for bisect is the efficient update of an already ordered list.
You may want either to change the data format of your list (e.g. maintaining it in direct order as much as possible, and then reversing it at the very end), either to implement your own version of bisect.
Or, if you are not in the main usecase, you can opt not to use it at all, e.g. by inserting all elements and then sorting them at the very end.

Answer 6

One approach is to negate the keys. For example,

a = [1,2,3,4]
a.reverse()
def comparator(a):
    return -a
b = [comparator(i) for i in a]
bisect.insort_right(b,comparator(2.5))
a = [comparator(c) for c in b]

Result: [4, 3, 2.5, 2, 1]

Answer 7

To complete Dennis Golomazov's answer, if you ever need reverse_bisect_left,
you can use:

def reverse_bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, 
    assuming a is sorted in descending order.

    The return value i is such that all e in a[:i] have e > x, and all e in
    a[i:] have e <= x. 
    So if x already appears in the list, a.insert(x) will
    insert just after the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.

    Essentially, the function returns number of elements in a which are > than x.
    """
    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]: # this was just > in bisect_right  
            hi = mid
        else: lo = mid+1
    return lo

Answer 8

I've never used to the bisect package. But if it only works in ascending order and you're always keeping your list sorted (whether ascending or descending) then you could simply sort beforehand and then invert (if you want to keep it descending).

x.sort()
bisect.insort(x,2.5)
x.reverse()

Obviously more a hack then a real solution but at least it would work.

Answer 9

Hopefully the "key" argument will be added to bisect module functions one day (see: http://bugs.python.org/issue4356). Unfortunately it's not possible without some kind of workaround at the moment (Python version < 3.4).

One possible workaround is to use a wrapper like:

class ReversedSequenceView(collections.MutableSequence):
    def __init__(self, seq):
        self._seq = seq

    def __getitem__(self, i):
        return self._seq[-1 - i]

    def __setitem__(self, i, v):
        self._seq[-1 - i] = v

    def __delitem__(self, i):
        del self._seq[-1 - i]

    def __len__(self):
        return len(self._seq)

    def insert(self, i, v):
        return self._seq.insert(len(self._seq) - i, v)

Usage:

>>> x = [4., 3., 2., 1.]
>>> bisect.insort(ReversedSequenceView(x), 2.5)
>>> x
[4.0, 3.0, 2.5, 2.0, 1.0]

Answer 10

I had the same problem and since when I used ordered list.

I ended up with solution where I kept original list always in ascending order and just used reversed iterator when I needed to have descending order values.

This might not work with your problem...

Answer 11

You can insert like this

bisect.insort_left(lists, -x)

and extract elements like this

value = - lists[i]

Answer 12

I was looking to get the position to insert a number in a list, to keep it ordered. I ended up using the following solution:

def rev_bisect(l, v):
    '''l -> list (descending order)
       v -> value
    Returns:
       int -> position to insert value in list keeping it sorted
    '''
    h = list(range(len(l))) + [len(l)+1]
    h.reverse()
    l.reverse()
    return h[bisect.bisect_left(l, v)]