Each Answer to this Q is separated by one/two green lines.

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.

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)
```

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)
```

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
```

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.

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]

In Python 3.10, `insort`

gain a `key`

parameter, from the documentation:

keyspecifies 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]
```

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…

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]
```

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.

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
```

You can insert like this

`bisect.insort_left(lists, -x)`

and extract elements like this

```
value = - lists[i]
```

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)]
```