搜索或者查找是很重要的一类计算问题（另外一类比较重要的就是排序）。这应该是很多互联网笔试面试所热衷的一类问题，尤其是二分搜索，小编也多次面试过或者被面试过哦。
搜索，简而言之，就是判断一个对象k是否存在于list L中（用in可以实现）。通常情况下，如果存在，会求解k的索引（用L.index()可以实现）。
对于list相关的搜索函数，主要有以下几个：
elem in L：如果L中存在elem则为True否则为False；
L.index(elem)：返回L中第一次出现elem的索引；如果不在L中，则返回error；
L.count(elem)：返回elem出现在L中的次数；
min(L),max(L)：返回L中的最小值或者最大值。
如果L是无序的，那么我们只能逐一搜索L中的对象，算法的复杂度正比于list的长度，最差为list的长度。这称为线性搜索，刚刚几个函数都是基于线性搜索，因为任何的list都可以使用这些函数来完成搜索。
如果L是有序的，那么便可以用二分搜索（二分查找，折半查找）来完成搜索。二分搜索比线性搜索的性能高的多。假设L是升序的，比较k与L的中间位置的对象的大小，分为三种情况：
A、k == L[middle]，完成了搜索；
B、k < L[middle]，需要搜索L的前半部分；
C、k > L[middle]，需要搜索L的后半部分。
由此可见，当完成一次比较，要搜索的范围减少了1/2（对于线性搜索，每次比较后，要搜索的范围减少了常数1）。
在完成二分搜索时，我们保存两个变量left和right，L[left ... right]就是我们需要搜索的范围（初始化时left = 0，right = len(L)-1）。这时，k需要与搜索范围中间的对象，即索引为mid = (left + right)/2 的对象进行比较。比较后，我们搜索前半部分right = mid - 1 或者搜索后半部分 left = mid + 1。
二分搜索的Python代码如下：
# This is a function that returns the index of k if k is in L
# and returns -1, otherwise. The function assumes that L is
# sorted in ascending (non-decreasing) order and implements
# the binary search algorithm
def binarySearch(L, k):
left = 0
right = len(L) - 1
# iterate while there is a sublist that needs to be searched
while left <= right:
mid = (left + right) / 2 # index of the middle element
# Comparisons and then adjusting the boundaries of
# the sublist, if necessary
if L[mid] == k:
return mid # element is found at mid, so return this index
elif L[mid] < k: # look for element in right half
left = mid + 1
elif L[mid] > k: # look for element in the left half
right = mid - 1
return -1 # element is not found in the list
我们考察一下算法复杂度。由于每进行一次比较，搜索范围变为原来的1/2，假设L的长度为N，那么经过t次比较后，搜索范围变为N/2^(t)。当搜索范围变为1时，算法结束：N = 2^(t)。所以，算法复杂度为 t = log2(N)。
最后，让我们通过简单的计算来感受二分搜索的高效与魅力吧！
假设有N个随机产生的1到N之间的整数，如何得到不重复的整数呢？请看一下运行时间差异：
import random
L = []
for i in range(50000):
print i
L.append(random.randint(1,50000))
count = 0
for e in range(1, 50001):
if e in L:
count = count + 1
在上述建立L并完成线性搜索判断的过程中：建立L耗时0.78s，线性搜索判断的耗时为29.833s。
下面看一下二分搜索：
import random
L = []
for i in range(50000):
L.append(random.randint(1,50000))
L.sort()
count = 0
for e in range(1, 50001):
if binarySearch(L, e) >= 0:
count = count + 1
print count
在上述建立L并完成二分搜索判断的过程中：建立L耗时0.79s，排序耗时0.031s，二分搜索判断耗时0.169s。
你发现耗时的巨大差距了吗？ 你看到二分搜索的巨大魅力了吗？
