多语言展示
当前在线:541今日阅读:183今日分享:19

[Python3算法(5)] 递归实现二分查找算法[TZZ]

大家好!今天我给大家介绍一下通过递归方式实现二分查找算法的方法。分析二分查找算法的描述,你会发现其处理过程本身就是分而治之的思想,每次都将目标列表缩小一半,然后继续二分查找,直到找到元素或者列表为空(即基线条件)。如果您觉得这篇教程有帮助,请为我投上宝贵的一票(顺便求个“关注”),谢谢!32PyCharm安装教程[TZZ]0[Python3算法(1)] 二分查找算法[TZZ]
工具/原料
1

已安装PyCharm 2017.3软件(或以上版本);

2

已掌握“[Python3算法(1)] 二分查找算法[TZZ]”;

方法/步骤
1

启动PyCharm软件,新建一个名为“AlgorithmDemo5”的“Pure Python项目”,然后向项目中添加一个名为“main.py”的Python文件(具体步骤请参考引用教程);

2

在main.py文件中定义一个“binary_search_val_asc函数”,它需要传入一个升序排序的列表、指示该列表中子列表的起始索引位置和需要查找值。该函数采用递归方式实现二分查找过程,其查找过程与普通的二分查找类似,仅仅是在处理子列表时采用了递归调用。另外,需要注意子列表是否为空的检测,它是在调用下次递归之前进行的;

3

继续在main.py文件中定义一个以递归方式实现的二分查找函数binary_search_val_dec。与前一个函数不同的是,它需要一个降序排列的列表作为参数。其内部实现中,选择子列表的规则与前一个函数正好相反,但是基线条件相同;

4

继续在main.py文件中定义二分查找函数binary_search_rec。该函数封装了前两个函数的功能,其调用接口更加的简洁;

5

在main.py文件中添加二分查找函数的测试代码。在这份代码中,定义了一个测试列表,然后打印该列表以及其升序排列后的列表。最后,采用for循环,通过binary_search_rec函数从测试列表中查找从-10~10的值,并输出查找结果;

6

测试代码编写完毕后,调试运行程序。在弹出的控制台窗口中,可以见到打印的查找结果。与之前打印的升序列表对比,人工检测算法是否处理正确;

7

关闭控制台窗口返回到main.py文件中,继续添加从降序列表中二分查找元素的测试代码,然后调试运行程序;

8

在弹出的控制台窗口中,可以见到输出的查找结果。通过人工将结果与降序列表核对,可以确定算法是否执行正确;

9

递归二分查找算法代码的实现要点是检测子列表是否为空,即子列表索引的开始索引大于结束索引或者结束索引小于开始索引。另一个小技巧就是用一个接口更简洁的函数充当外观函数,这样用户使用起来会更方便。Enjoy!

推荐信息