前言

其實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