当前位置: > python教程 > python基础教程 >

python二分查找算法
栏目分类:python基础教程   发布日期:2019年06月06日 17:23:42   浏览次数:

什么是二分查找
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。
输入是一个有序的元素列表,查找的元素是否能找到,二分查找返回其位置;否则返回null。
 

假如我现在脑海中想到一个1-100的列表,需要你以最小的次数猜一下我喜欢哪一个数字,你每一次猜测后,我会说你猜的数字小了,大了或者猜对了。假设你从1开始依次猜.猜测过程会是1,2,3,4,5...100。这就是简单查找,是最笨的方法,每次猜测都只能排除一个排除一个数字,如果我想的是99的话,需要猜99次才能猜到。我们把这种叫做顺序查找

 在来看下使用二分查找

       如果有100个数,对半,也就是50,要查找到数和50位置上的数进行比较,如果相等,就找到了,不相等,看下这个数比50上的数大还是小,如果是小,那就查找前50的数,在进行对半,如果是大,那就查找后50的数,在对半,缩小范围因此,不管我心里面想的是什么数字,都可以在7次之内猜到,因为每猜一次都可以排除一半的数字。

假设在一个列表含有240000个身份证号码,需要查找一个身份证,如果使用之前的简单查找,估计会懵逼。

    一般而言,对于包含n个元素的列表,用二分查找只需要logn步,而简单查找最多需要n步。

 

代码实现二分查找
 

def bin_search(data_list, val):
    low = 0                         # 最小数下标
    high = len(data_list) - 1       # 最大数下标
    while low <= high:
        mid = (low + high) // 2     # 中间数下标
        if data_list[mid] == val:   # 如果中间数下标等于val, 返回
            return mid
        elif data_list[mid] > val:  # 如果val在中间数左边, 移动high下标
            high = mid - 1
        else:                       # 如果val在中间数右边, 移动low下标
            low = mid + 1
    return # val不存在, 返回None

my_list=[1,2,3,4,5,6,7,8,9]
ret = bin_search(my_list, 3)   #能够查到
print('返回查到的下示:',ret)
ret = bin_search(my_list, 0)
print('返回查到的下示:',ret)  #没有查到

运行结果:

 

返回查到的下示: 2

返回查到的下示: None


现在明白二分查找怎么实现了吧,如果还不明白,可以加我微信ziwenseo,在给你讲

 


相关热词:

热门关键词
python字符串
     
python教程 python爬虫 python人工智能 Python+大数据 python问答