Question

前文中已经暗示了，如果我们先对我们的数据进行排序，使得所有位于某个元素左边的其他元素都小于（或大于）它，那么就可以获得更好的搜索性能。对象的比较是通过对象的魔法函数__eq__和__lt__进行的，用户对象可以自定义这两个函数。

　备忘　

没有__eq__和__lt__方法，一个用户对象就只能跟同类型的对象比较且比的是对象实例在内存中的地址。

高效搜索必需的两大要素是排序算法和搜索算法。Python列表有一个内建的排序算法使用了Tim排序。Tim排序可以在最佳情况下以O(n)（最差情况下则是O(n log n)）的复杂度排序。它运用了多种排序算法。对于给定的数据，它使用探索法猜测哪个算法的性能最优（更确切地说，它混用了插入排序和合并排序算法）来达到这样的性能。

一旦一个列表被排序，我们就可以用二分搜索找到我们的目标（例3-3），其平均情况复杂度是O(log n)。它首先查询位于列表中点的值并和目标值比较。如果中点值小于目标值，我们就继续考察右半边列表，我们不断将列表二分，直至找到目标值或发现该值不存在于列表。结果就是我们不需要像线性搜索那样读取列表中所有的元素，而仅仅读取了一个子集。

例3-3　对已排序列表的高效搜索——二分搜索

def binary_search(needle, haystack):
  imin, imax = 0, len(haystack)
  while True:
    if imin >= imax:
      return -1
    midpoint = (imin + imax) // 2
    if haystack[midpoint] > needle:
      imax = midpoint
    elif haystack[midpoint] < needle:
      imin = midpoint+1
    else:
      return midpoint

这个方法使得我们无须求助重量级的字典解决方案就能够查找列表中的元素。特别是当列表本身就已经排过序的情况下，用二分搜索进行对象查找（复杂度O(log n)）比将列表转换成字典然后进行查询要更高效（虽然字典查找复杂度是0(1)，字典转换复杂度却是O(n)。而且字典要求没有重复的键，你可能不希望受到这样的限制）。

另外，使用bisect模块可以进一步简化这一流程，它提供了一个简便的函数让你可以在保持排序的同时往列表中添加元素，以及一个高度优化过的二分搜索算法函数来查找元素。它提供的函数可以将新元素直接插入正确的排序位。在列表始终排序的情况下，我们可以轻松找到需要的元素（示例代码可以在bisect模块的文档中找到）。另外，我们可以非常迅速地用bisect找到跟我们的目标值最接近的元素（例3-4）。这个功能对于比较两个相似但不完全一样的数据集来说极其有用。

例3-4　用bisect模块在列表中查询最接近目标的值

import bisect
import random

def find_closest(haystack, needle):
  # bisect.bisect_left will return the first value in the haystack
  # that is greater than the needle
  i = bisect.bisect_left(haystack, needle)
  if i == len(haystack):
    return i - 1
  elif haystack[i] == needle:
    return i
  elif i > 0:
     j = i - 1
    # since we know the value is larger than needle (and vice versa for the
    # value at j), we don't need to use absolute values here
     if haystack[i] - needle > needle - haystack[j]:
      return j
  return i

important_numbers = []
for i in xrange(10):
  new_number = random.randint(0, 1000)
  bisect.insort(important_numbers, new_number)

# important_numbers will already be in order because we inserted new elements
# with bisect.insort
print important_numbers

closest_index = find_closest(important_numbers, -250)
print "Closest value to -250: ", important_numbers[closest_index]

closest_index = find_closest(important_numbers, 500)
print "Closest value to 500: ", important_numbers[closest_index]

closest_index = find_closest(important_numbers, 1100)
print "Closest value to 1100: ", important_numbers[closest_index]

总的来说，本节涉及了编写高效代码的基本原则：选择正确的数据结构并坚持使用它！虽然对于某个特定操作来说也许还存在更高效的数据结构，但是在这些数据结构之间进行转换的代价可能会抵消效率上的增益。