二分查找算法介绍

拼搏现实的明天。 2023-06-14 04:14 6阅读 0赞

二分查找算法的实现过程如下：在排序数组中查找某一个数据项，首先让待查数据与中间下标元素开始比较，如果相等则返回，如果小于中间下标元素，重新开始从低位开始，(中间下标-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;
    	}
    }

运行程序，打印结果如下所示：

![20191118143946321.png][]

如果查询一个不存在的元素，比如98，结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

关于二分查找在一般的面试中会经常问到，笔试题也会出现，是一个面试基本也是必备的算法。至于它的复杂度，我们可以这样来推算，至少是n/2，但是这还不是最科学的，理论上最坏的情况是所有的折半均执行一次才结束，因此是一个log2(n)：以2为底数，n的对数。一般也直接写作log(n)。

前面的原理说了，二分查找的前提是数组是排序的，所以他的适用范围是有限制的，但是他的应用却是最广泛的，这得益于他的查询效率。

[20191118143946321.png]: https://img-blog.csdnimg.cn/20191118143946321.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/201911181441550.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk=,size_16,color_FFFFFF,t_70