Python实现二分查找与bisect模块详解

前言

其实Python 的列表（list）内部实现是一个数组，也就是一个线性表。在列表中查找元素可以使用 list.index() 方法，其时间复杂度为O(n) 。对于大数据量，则可以用二分查找进行优化。

二分查找要求对象必须有序，其基本原理如下：

      1.从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；

      2.如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

      3.如果在某一步骤数组为空，则代表找不到。

二分查找也成为折半查找，算法每一次比较都使搜索范围缩小一半， 其时间复杂度为 O(logn)。

我们分别用递归和循环来实现二分查找：

def binary_search_recursion(lst, value, low, high):  if high < low:  return None mid = (low + high) / 2  if lst[mid] > value:  return binary_search_recursion(lst, value, low, mid-1)  elif lst[mid] < value:  return binary_search_recursion(lst, value, mid+1, high)  else:  return mid def binary_search_loop(lst,value):  low, high = 0, len(lst)-1  while low <= high:  mid = (low + high) / 2  if lst[mid] < value:  low = mid + 1  elif lst[mid] > value:  high = mid - 1 else: return mid  return None

接着对这两种实现进行一下性能测试：

if __name__ == "__main__": import random lst = [random.randint(0, 10000) for _ in xrange(100000)] lst.sort() def test_recursion(): binary_search_recursion(lst, 999, 0, len(lst)-1) def test_loop(): binary_search_loop(lst, 999) import timeit t1 = timeit.Timer("test_recursion()", setup="from __main__ import test_recursion") t2 = timeit.Timer("test_loop()", setup="from __main__ import test_loop") print "Recursion:", t1.timeit() print "Loop:", t2.timeit()

执行结果如下：

Recursion: 3.12596702576Loop: 2.08254289627

可以看出循环方式比递归效率高。

bisect 模块

Python 有一个 bisect 模块，用于维护有序列表。bisect 模块实现了一个算法用于插入元素到有序列表。在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect 是二分法的意思，这里使用二分法来排序，它会将一个元素插入到一个有序列表的合适位置，这使得不需要每次调用 sort 的方式维护有序列表。

下面是一个简单的使用示例：

import bisectimport randomrandom.seed(1)print'New Pos Contents'print'--- --- --------'l = []for i in range(1, 15): r = random.randint(1, 100) position = bisect.bisect(l, r) bisect.insort(l, r) print'%3d %3d' % (r, position), l