我们常用于猜数字游戏的二分查找算法怎么用python实现呢?

原理简单介绍

类比猜数游戏

我们上篇文章唠了唠经典的冒泡排序算法,如果说经典算法,那怎么少得了二分查找呢.可以说它是经典中的经典,就我们常用于猜数字方法.就是他.比如猜 1 到 100 的数字,目标数字的 34.这时候你就猜一个数 50,出题人会跟你说是大了还是小了.明显你猜的 50 比 34 大,那出题人就会跟你说你猜的数大了,那你可猜的数的范围变小了.变成了 1-49,你继续猜 25,这时候猜的数小了,猜数范围变成 26-50,你继续猜 38,范围缩小到 26-38.你继续猜 32,范围缩小到 33-38,你继续对半猜 35,范围变成 33-34,这时候最多两轮你就猜到目标数了,6 轮就可得出目标数,不过在游戏中还是有次数限制的,这就是经典的猜数字游戏

游戏代码如下:

限制只能猜五次

digital=int(input('请设定猜数的数值:'))
if 1<=digital<=100:
   print(digital)
else:
   print('无效数值，请重新输入1-100以内的数值') #输入数值

for g in range(1,6):
    guess=int(input('请输入第%d次猜的数值为:'%g))
    if guess==digital:
        print('恭喜你，猜对了')
        break
    elif g==5:
        print('很遗憾，你的次数已用完')
    elif guess<digital:
        print('猜小了')
    elif guess>digital:
        print('猜大了')

言归正传,那具体二分法是怎么实现的呢?

二分查找的原理

简单说二分查找就是把一堆东西,折半分,缩小查找范围,直到找到目标为止.

不过二分查找法需要符合一定条件.二分查找法作用于一个有序数据集合上,所以要注意的是有序,首先要查找的是有序集合的中间元素,如果中间元素比要查找的元素大,接着转向较小的半集进行查找,反之,若中间元素比要查元素小,则转向较大的半集进行查找,转进范围更小的数据集后重复这个查找步骤.直到招到要查找的元素或数据集不能再分割.

这就是传说中的经典算法--二分查找.二分查找实质上就是不断地将有序数据集对半分割,并检查分区中的中间元素,是不是跟我们上面的猜数字游戏差不多呢?

见证奇迹的时刻--实操

下面我们就通过实例来检验上面的原理,我们现在有一个有序集合:[12,16,17,19,20],我们要从中查找 16 这个元素

下面我们就先通过图示来展示一下查找过程

图中的 low 和 high 是用来控制查找元素的两个边界值,下面[12,16,17,19,20]就是要查找的有序数据集合,mid 表示的是 low 和 high 之间的中间值,接着我们就按照图示进行代码实现:

lists = [12,16,17,19,20]
val = 16
low = 0
high = len(lists) - 1
trace = False
while low <= high:
    mid = (low + high) // 2
    if lists[mid] == val:
        trace = True
        break
    elif lists[mid] > val:
        high = mid - 1
    else:
        low = mid + 1

if trace:
    print("找到 {0} 的索引是 {1}".format(val, mid))
else:
    print("没有找到 {0}".format(val))

总结

随着循环不断推进,low 从左向右移,high 从右往左移,更新搜索范围,当 mid 找到目标时,将 trace 标记为 True,并跳出循环.如果目标一直没有找到,那 low 和 high 的指向将会重合并退出循环.