二分查找算法简述

问题引入

假设我们要从一个电话簿中查找一个以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

相关推荐