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

作者：迷彩

2022 年 7 月 25 日
本文字数：1210 字
阅读完需：约 4 分钟

原理简单介绍

类比猜数游戏

我们上篇文章唠了唠经典的冒泡排序算法,如果说经典算法,那怎么少得了二分查找呢.可以说它是经典中的经典,就我们常用于猜数字方法.就是他.比如猜 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 = 16low = 0high = len(lists) - 1trace = Falsewhile 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))