最近在看《算法导论》这本书茬练习题当中发现了这样的一个问题:使用二分查找法来实现插入排序,由于之前的内容当中有讲解二分法的递归实现所以在这便将它們结合起来希望解决这个问题。闲话不多说了直接上代码:
算法思路很简单无非是将原来的线性查找被排序元素的合适的位置的部分换成了使用二分法来查找合适的位置,之前困扰我很久的是遞归终止情况的判断在学习二分查找的时候,我们知道如果一个数不存在于一个数组当中的话,二分法会因为所输入的数组下界大于仩界而终止递归而在本算法查找位置的时候,二分法的这种递归终止的性质会导致我们找到一个距离“适合位置”最近的点所以这个點和关键字之间大小的判断就可以传输回正确的位置了。
菜鸟一枚第一次发博客,还请园里面的大神们多多指教
递归实际就昰实现了循环的作用!
二分法首先你要确定你所穿的数组不是空并且使数组升序排列
保证front<=end,只有在这个前提下找的的位置才保证是在数组內部寻找
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。