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

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

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

二分查找算法

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

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

输出结果为：

当查找元素为key=13时，其输出结果为：

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

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

输出结果为：

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

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

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

二分排序算法

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

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

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

输出结果为：

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

输出结果为：

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

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

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

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

刘三少爷的剑