原理简单介绍
类比猜数游戏
我们上篇文章唠了唠经典的冒泡排序算法,如果说经典算法,那怎么少得了二分查找呢.可以说它是经典中的经典,就我们常用于猜数字方法.就是他.比如猜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 + 1if trace: print("找到 {0} 的索引是 {1}".format(val, mid))else: print("没有找到 {0}".format(val))
总结
随着循环不断推进,low从左向右移,high从右往左移,更新搜索范围,当mid找到目标时,将trace标记为True,并跳出循环.如果目标一直没有找到,那low和high的指向将会重合并退出循环.