二分查找算法简述
问题引入
假设我们要从一个电话簿中查找一个以L打头的人,可以从头开始翻页,直接进入L打头的部分。但我们可能不这么做,我们可能从中间开始,因为我们知道以L打头的名字在电话簿的中间;再假设我们从字典中查找一个以字母O打头的单词,我们也将从中间开始查找。 如果现在假设你要登录Facebook,当你这样做的时候,Facebook必须核实你的是否具有该网站的注册账户信息,因此他会从数据库中查找你的用户名,假设你的用户名为sunyboy,Facebook可以以A打头开始查找,更合乎逻辑的做法是从中间开始查找。
这是一个查找的问题,在上述所有请情况下,都可以使用同一种算法来解决问题,这种算法是二分查找。
概念
二分查找是一种算法,其输入是一个有序的元素列表。如果要查找的元素包含在列表中,二分查找返回其位置,否则返回null。
基本原理
通过一个实例来说明二分查找的原理;
你随便想一个1~100的数字,我的目标是以最少的次数猜到该数字。我每次猜测之后,你会说小了、大了或对了。
假设我从1开始猜测,这样一个一个数字猜测,每次猜测都只能排除一个数字。如果你想的数字是99,我得猜测99次才能猜到!这是简单查找,更准确的说法就是傻找;
最佳的方法是从这个数字1~100之间取中间数,这样就可以排除一半的数字!我知道1~50都小了,我会去猜测75,你说数字大了,我会去猜测63,你说大了,我会猜测57,这就猜对了;这种查找方法会在7次内猜测出答案,这个7又是如何得来的呢? 一般而言,对于包含n个元素的列表,用而二分查找最多需要log2n(对数:例:2^3=8 <-> log28=3 )步,而简答查找最多需要n步;
代码示例
__Author__ = "ZhiChao Ma"
#versions:python3.5.2
#使用二分查找法快速从一个数组中查找一个指定元素,并返回该元素的索引值
def binary_search(list, item):
#low和high用于跟踪要在其中查找的列表部分
low = 0
high = len(list)-1
while low <= high: #只要范围没有缩小到只包含一个元素
#如果(low + high)不是偶数,python自动向下取整,这里来检查中间元素
mid = (low + high)
guess = list[mid]
if guess == item: #找到了元素
return mid
if guess > item: #猜的数字大了
high = mid -1
else: #猜的数字小了
low = mid + 1
return None #没有指定元素
my_list1 = ['zhangsan', 'lisi', 'wangwu',]
my_list2 = list(range(10000))
print(binary_search(my_list1, 'lisi'))
print(binary_search(my_list2, 5002))
print(binary_search(my_list2, -110))
输出结果:
1
5002
None