二分查找可以用于降序排列的列表吗？

Question

我该如何在降序排列的列表上使用bisect模块呢？比如：

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   

这个模块里只有insort（insort_right）和insort_left这两个方法，但对我来说都不管用。

Answer 1

稍微更新了一下 bisect 库的代码：

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 2

在Python 3.10中，insort这个函数新增了一个叫做key的参数，具体内容如下：

key是一个函数，它接收一个参数，用来从每个输入元素中提取出用于比较的关键值。默认情况下，这个值是None，也就是说直接比较元素本身。

所以，如果你想在一个按降序排列的列表中插入元素，可以这样做：

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) 

输出结果

[4.0, 3.0, 2.5, 2.0, 1.0]

Answer 3

最简单的方法可能就是借用库里的代码，然后自己做一个版本。

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)