• bisect —- 数组二分查找算法
    • 搜索有序列表
    • 其他示例

    bisect —- 数组二分查找算法

    源代码：Lib/bisect.py

    这个模块对有序列表提供了支持，使得他们可以在插入新数据仍然保持有序。对于长列表，如果其包含元素的比较操作十分昂贵的话，这可以是对更常见方法的改进。这个模块叫做 bisect 因为其使用了基本的二分（bisection）算法。源代码也可以作为很棒的算法示例（边界判断也做好啦！）

    定义了以下函数：

    • bisect.bisectleft(_a, x, lo=0, hi=len(a))
    • 在 a 中找到 x 合适的插入点以维持有序。参数 lo 和 hi 可以被用于确定需要考虑的子集；默认情况下整个列表都会被使用。如果 x 已经在 a 里存在，那么插入点会在已存在元素之前（也就是左边）。如果 a 是列表（list）的话，返回值是可以被放在 list.insert() 的第一个参数的。

    返回的插入点 i 可以将数组 a 分成两部分。左侧是 all(val < x for val in a[lo:i]) ，右侧是 all(val >= x for val in a[i:hi]) 。

    • bisect.bisectright(_a, x, lo=0, hi=len(a))
    • bisect.bisect(a, x, lo=0, hi=len(a))
    • 类似于 bisect_left()，但是返回的插入点是 a 中已存在元素 x 的右侧。

    返回的插入点 i 可以将数组 a 分成两部分。左侧是 all(val <= x for val in a[lo:i])，右侧是 all(val > x for val in a[i:hi]) for the right side。

    • bisect.insortleft(_a, x, lo=0, hi=len(a))

    • 将 x 插入到一个有序序列 a 里，并维持其有序。如果 a 有序的话，这相当于 a.insert(bisect.bisect_left(a, x, lo, hi), x)。要注意搜索是 O(log n) 的，插入却是 O(n) 的。

    • bisect.insortright(_a, x, lo=0, hi=len(a))

    • bisect.insort(a, x, lo=0, hi=len(a))
    • 类似于 insort_left()，但是把 x 插入到 a 中已存在元素 x 的右侧。

    参见

    SortedCollection recipe 使用 bisect 构造了一个功能完整的集合类，提供了直接的搜索方法和对用于搜索的 key 方法的支持。所有用于搜索的键都是预先计算的，以避免在搜索时对 key 方法的不必要调用。

    搜索有序列表

    上面的 bisect() 函数对于找到插入点是有用的，但在一般的搜索任务中可能会有点尴尬。下面 5 个函数展示了如何将其转变成有序列表中的标准查找函数

    1. def index(a, x):
    2.     'Locate the leftmost value exactly equal to x'
    3.     i = bisect_left(a, x)
    4.     if i != len(a) and a[i] == x:
    5.         return i
    6.     raise ValueError
    7.  
    8. def find_lt(a, x):
    9.     'Find rightmost value less than x'
    10.     i = bisect_left(a, x)
    11.     if i:
    12.         return a[i-1]
    13.     raise ValueError
    14.  
    15. def find_le(a, x):
    16.     'Find rightmost value less than or equal to x'
    17.     i = bisect_right(a, x)
    18.     if i:
    19.         return a[i-1]
    20.     raise ValueError
    21.  
    22. def find_gt(a, x):
    23.     'Find leftmost value greater than x'
    24.     i = bisect_right(a, x)
    25.     if i != len(a):
    26.         return a[i]
    27.     raise ValueError
    28.  
    29. def find_ge(a, x):
    30.     'Find leftmost item greater than or equal to x'
    31.     i = bisect_left(a, x)
    32.     if i != len(a):
    33.         return a[i]
    34.     raise ValueError

    其他示例

    函数 bisect() 还可以用于数字表查询。这个例子是使用 bisect() 从一个给定的考试成绩集合里，通过一个有序数字表，查出其对应的字母等级：90 分及以上是 'A'，80 到 89 是 'B'，以此类推

    1. >>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):
    2. ...     i = bisect(breakpoints, score)
    3. ...     return grades[i]
    4. ...
    5. >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
    6. ['F', 'A', 'C', 'C', 'B', 'A', 'A']

    与 sorted() 函数不同，对于 bisect() 函数来说，key 或者 reversed 参数并没有什么意义。因为这会导致设计效率低下（连续调用 bisect 函数时，是不会 "记住" 过去查找过的键的）。

    正相反，最好去搜索预先计算好的键列表，来查找相关记录的索引。

    1. >>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
    2. >>> data.sort(key=lambda r: r[1])
    3. >>> keys = [r[1] for r in data]         # precomputed list of keys
    4. >>> data[bisect_left(keys, 0)]
    5. ('black', 0)
    6. >>> data[bisect_left(keys, 1)]
    7. ('blue', 1)
    8. >>> data[bisect_left(keys, 5)]
    9. ('red', 5)
    10. >>> data[bisect_left(keys, 8)]
    11. ('yellow', 8)