python实现二分查找算法/二分排序算法

二分法可以分为三类:二分查找算法、二分排序算法、二分合并算法。

本文分别基于循环和递归实现二分查找算法,然后对比介绍并实现了插入排序算法和二分排序算法。

二分查找算法

二分查找又被称为折半查找。假设我们有一个列表,要在该列表中查找某一个元素,我们需要先对该列表进行排序(假设是从小到大的排序),然后取这个列表的中值与待查找的元素进行比较,如果该元素等于中值,则查找成功;如果该元素大于中值,则接下来在右边的子表(之前二分出来的两个子表中的右边子表)中继续进行以中值为中心的折半查找;如果该元素小于中值,则在左边的子表中继续进行以中值为中心的折半查找…如此循环,直到查找到目标元素,此时查找成功,或者直到子表再也不能进行二分为止,此时查找不成功。

我们在列表[1,5,9,3,6,12,7,25,10]中查找元素12,其基于循环的python实现如下:

输出结果为:

当查找元素为key=13时,其输出结果为:

二分查找算法直观上属于一种“持续的折半查找”,它被层层拆解为一个个子问题,与递归的思维非常吻合。所以,我们也完全可以基于递归算法来实现二分查找。

二分查找算法基于递归算法的python实现如下:

输出结果为:

可以发现元素12的序号和基于循环的方法不一致,这是因为二分产生的子序列是由原序列切片产生的新序列。

同样地,当查找元素key=13时,输出结果为:

即在序列中没有查找到元素13。

二分排序算法

前面的文章中我们从扑克牌的排序原理着手,然后用python实现了插入排序。二分排序算法就是在插入排序的基础上进行改进的一种算法,所以二分排序又称为折半插入排序。

当直接插入排序进行到某一趟时,已经实现了一部分的有序,此时不再继续使用插入排序算法,而对前面已经实现有序的部分采用折半二分查找,找出下一个元素应该插入的位置,即一部分的插入排序加上一部分的二分查找插入后续元素,这就是我们所说的折半插入排序,是一种稳定的排序算法,其元素的比较次数因为采用折半查找而减少。

我们首先得到插入排序算法的python实现:

输出结果为:

然后我们对二分排序算法进行python实现:

输出结果为:

可见,二分排序算法同样实现了符合预期的输出。

插入排序和二分排序虽然能实现同样的效果,但它们需要的时间复杂度是不一样的,我们分别通过如下的计时语句来实现插入排序和二分排序的计时:

当将进行排序的元素个数增大到20000时,可以明显地观察到两种方法的时间对比:

通过结果可知,二分排序方法比插入排序方法快太多!

刘三少爷的剑

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180730G1ZT9R00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励