二分查找算法的实现过程如下:在排序数组中查找某一个数据项,首先让待查数据与中间下标元素开始比较,如果相等则返回,如果小于中间下标元素,重新开始从低位开始,(中间下标-1)结束的数组内,继续执行相同的查找操作,如果大于中间下标元素,重新开始从中间下标+1,高位结束的数组内,继续执行相同的查找操作,直到低位超过高位,如果没有找到,返回-1,如果找到,则返回对应的中间下标。因为每次执行一次查询操作,查找范围会减少一半,所以二分查找也叫折半查找。
二分查找算法的前提是数组必须是排好序的,如果是乱序的,二分查找不适用。如果是仅仅查找元素是否存在,可以考虑将乱序的数组排序,然后使用二分查找,但是查找的下标不能作为最终计算的依据,只能作为元素存在的依据。
二分查找的思路很特别,就是不断的从原始数组中进行范围缩小式的查找,基于这种原理,二分查找算法的实现可以使用循环的方式实现,也可以使用递归的方式实现。关键点是计算中间下标,以及算法终止的条件。中间下标计算方式:mid=(low+high)/2,最开始low=0,high=size(array)-1,之后根据比较结果,low或者high会发生变化。终止条件low>high。根据这些思路,我们给出二分查找的示例代码:
#include <iostream.h>
int search_by_loop(int *arr,int low,int high,int item){
while(low<=high){
int mid = (low+high)/2;
cout<<"mid = "<<mid<<endl;
if(item<arr[mid]){
high = mid-1;
}else if(item>arr[mid]){
low = mid+1;
}else{
return mid;
}
}
return -1;
}
int search_by_recursive(int *arr,int low,int high,int item){
if(low>high)
return -1;
int mid = (low+high)/2;
cout<<"mid = "<<mid<<endl;
if(item==arr[mid]){
return mid;
}else if(item<arr[mid]){
return search_by_recursive(arr,low,mid-1,item);
}else{
return search_by_recursive(arr,mid+1,high,item);
}
}
void main(){
int data[] = {1,20,35,45,50,68,99,100,120,200};
int len = sizeof(data)/sizeof(data[0]);
int low = 0,high = len-1;
int index = search_by_loop(data,low,high,99);
if(index>-1){
cout<<"found item(99) at "<<index<<endl;
}else{
cout<<"not found."<<endl;
}
int index2 = search_by_recursive(data,low,high,99);
if(index2>-1){
cout<<"found item(99) at "<<index2<<endl;
}else{
cout<<"not found."<<endl;
}
}
运行程序,打印结果如下所示:
如果查询一个不存在的元素,比如98,结果如下:
关于二分查找在一般的面试中会经常问到,笔试题也会出现,是一个面试基本也是必备的算法。至于它的复杂度,我们可以这样来推算,至少是n/2,但是这还不是最科学的,理论上最坏的情况是所有的折半均执行一次才结束,因此是一个log2(n):以2为底数,n的对数。一般也直接写作log(n)。
前面的原理说了,二分查找的前提是数组是排序的,所以他的适用范围是有限制的,但是他的应用却是最广泛的,这得益于他的查询效率。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)