Python 二分法笔记

Python 二分法笔记

算法：最高效解决问题的办法 算法之二分法 需求：有一个按照从小到大顺序排列的数字列表

传统遍历方式

nums = [-3,4,7,10,13,21,43,77,89]for i in nums: if i == 10: print(i) break print(i) 打印：-34710# 找到10的时候才结束，这就是遍历，从左到右查询，这种效率是非常底的，万一我想要查找的值不是10，而是上万呢？难道还要遍历列表一个一个找？这不现实。

二分法算法方式

【前提是值的大小从左到右依次排序】#<==可以使用sort()先进行一个升序

二分法的原理就是先获取到列表中间的值，对比需要查找的值。 如果查找的值比中间值大了，则从中间值开始到左边的值全部切成新列表重新计算。 如果查找的指比中间值小了，则从中间值开始到右边的值全部切成新列表重新计算。 最后计算结果查找的值既不大于中间值也不小于中间值的时候，则证明找到了需要的值。 注意： 如果列表元素长度为奇数时，则取中间的那个值为中间值，如果为偶数时，取中间第一个值或者第二个值都是可以的，比如[1,2,3,4]，取2或者3都是可以当做中间值的。

'''列表'''nums = [-3,4,7,10,13,21,43,77,89]'''需要查找的值'''find_num = 10'''递归函数形参find_num接收需要查找的值和形参l列表'''def binary_search(find_num,l): '''在每一次查找时显示一次l列表内容''' print(l) '''将列表长度整除2，得到中间值的索引''' mid_index=len(l) //2 '''判断需要查找的值大于中间值，则返回True执行以下代码''' if find_num > l[mid_index]: '''将l列表从中间值开始往右全部切出来重新赋值给l列表，这里+1的原因是中间值已经不需要比较了，将中间值的索引+1''' l=l[mid_index+1:] '''递归函数将需要查找的值和切好的列表重新进入循环''' binary_search(find_num,l) '''判断需要查找的值小于中间值，则返回True执行以下代码''' elif find_num

bug优化

如果找的值在列表中不存在就会报错列表索引超出范围。

nums = [-3,4,7,10,13,21,43,77,89]find_num = 30def binary_search(find_num,l): print(l) mid_index=len(l) //2 if find_num > l[mid_index]: l=l[mid_index+1:] binary_search(find_num,l) elif find_num l[mid_index]: l=l[mid_index+1:] binary_search(find_num,l) elif find_num

#加油！！！！！！！！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。