bisect —- 数组二分查找算法

源代码: Lib/bisect.py


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

定义了以下函数:

bisect.bisect_left(a, x, lo=0, hi=len(a))

a 中找到 x 合适的插入点以维持有序。参数 lohi 可以被用于确定需要考虑的子集;默认情况下整个列表都会被使用。如果 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.bisect_right(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.insort_left(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.insort_right(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. def find_lt(a, x):
  8. 'Find rightmost value less than x'
  9. i = bisect_left(a, x)
  10. if i:
  11. return a[i-1]
  12. raise ValueError
  13. def find_le(a, x):
  14. 'Find rightmost value less than or equal to x'
  15. i = bisect_right(a, x)
  16. if i:
  17. return a[i-1]
  18. raise ValueError
  19. def find_gt(a, x):
  20. 'Find leftmost value greater than x'
  21. i = bisect_right(a, x)
  22. if i != len(a):
  23. return a[i]
  24. raise ValueError
  25. def find_ge(a, x):
  26. 'Find leftmost item greater than or equal to x'
  27. i = bisect_left(a, x)
  28. if i != len(a):
  29. return a[i]
  30. 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)