二分查找的定义
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
算法的要求
从上面的定义我们可以知道,满足该算法的要求必须如下两点:
- 必须采用顺序存储结构。
- 必须按关键字大小有序排列。
算法的步骤
其实,二分查找也还是比较容易理解的,大概就是一分为二,然后两边比较,保留有效区间,继续一分为二查找,直到找到或者超出区间则结束,所以二分查找的基本步骤是:
- 确定要查找的区间
- 确定要二分时的参照点
- 区间内选取二分点
- 根据二分点的值,综合左右区间情况以及求解的目的,舍去一半无用的区间
- 继续在有效区间重复上面的步骤
算法源码
这里,我主要采用递归和非递归两种方法实现,具体如下:
首先第一种是非递归的算法实现,算法如下:
1 | /** |
然后第二种是递归的算法实现,算法如下:
1 | /** |
算法的使用
需求是在一个排列好的区间($arr)中,查找一个数($number)的所在位置,所以,调用算法查找如下:
1 | // 待查找区间 |
时间复杂度分析
在有序数组中如果用暴力的算法去查找,也就是逐个遍历比较,那么时间复杂度是O(n);但是,用二分查找后,因为每次可以舍去一半查找区间,所以会将时间复杂度减少到O(logn),算法更优。
最后
又到了无聊的客套话时间,老规律,有问题直接留言,有想法直接说,有错误直接提出来,我都会及时回复的,谢谢。