先来玩个数字游戏,我从1~100中选一个整数,你来猜中这个数字。

如果你运气好的话可能十几次就猜中了,也可能是耐心的提问了我100次后。

但其实你只需要提问7次就可以找到答案。

举个例子,假设我选的数字是86

  • 问:这个数是否大于50?
    答:是
  • 问:大于75?
    答:是
  • 问:大于88?
    答:否
  • 问:大于82?
    答:是
  • 问:大于86?
    答:否
  • 问:大于84?
    答:是
  • 问:大于85?
    答:是

最终答案锁定,大于85并且不大于86,即86

连续将满足条件的值等分,直到找到正确答案,这就是二分法。
这个算法的本身就是递归的定义,也可以用递归来实现

  • 如果上下限相同,那么就是数字所在的位置,返回;
  • 否则找到两者的中间点,也就是上下限的平均值,查找数字在中间点的左侧还是右侧,然后继续查找数字所在的那半部分

下面实现一个二分法查找,返回查找目标数字所在序列的位置,下标。

#!/usr/bin/python
'''
二分法查找
sequence 查找的序列,范围
number   查找目标
lower    下限
upper    上限    
'''
def search(sequence, number, lower, upper):
	if lower == upper:
		assert number == sequence[upper]
		return upper
	else:
		middle = (lower + upper) // 2 #找到两者的中间点
		if number > sequence[middle]: 
			#如果在中间点的右侧,就在middle+1 ~ upper的范围内继续找
			return search(sequence, number, middle+1, upper)
		else:
			#如果在中间点的左侧,就在lower~middle的范围继续找
			return search(sequence, number, lower, middle)			
#初始化一个1~100的列表
seq = []
for x in xrange(1,101):
	seq.append(x)
print search(seq, 86, 0, 100)