二分查找的非递归与递归算法

电玩女神 2022-08-18 12:21 182阅读 0赞

一.引入:

假设一个已经\[排好序的数组a\[n\] ,若要搜索其中某个元素x,一般想到的是逐个查找,倘若x刚好在a\[n\],则最坏的情况需要n次比较,如若x不在数组a中,则更加得不偿失.

二分查找作为一个典型的分支策略,实现了对n个排好序的数组进行折半查找,每次取a\[n/2\]和x比较,找到则返回下标, 如果a\[n/2\]>x,由于是排好序的数组,则下一趟直接在0-n/2之间查找,else在a\[n/2\]-n查找.

二.函数:

//非递归查找

int Binsearch(char *a,int n,const char &x)	//二分查找,前提查找序列是有序排列
    {
    	int l=0,r=n-1,mid;			//数组下标从0开始
    	while(l<=r)
    	{
    		mid=(l+r)/2;
    		if(a[mid]==x)
    			return mid;
    		if(a[mid]<x)			//在右半区间查找
    			l=mid+1;
    		else 
    			r=mid-1;			//在左半区间查找
    	}
    	return -1;
    }

//递归查找

int Binsearch_Recursion(char *a, int l, int r,const char &x)	
    {
    	int mid;			//数组下标从0开始
    		mid=(l+r)/2;
    		if(a[mid]==x)
    			return mid;
    		if(a[mid]<x)			//在右半区间查找
    			return Binsearch_Recursion(a,mid+1,r,x);
    		else				//在左半区间查找
    			return Binsearch_Recursion(a,l,mid-1,x);			
    		if (l>=r)
    		return -1;
    }

三.程序代码:

#include<iostream>
    using namespace std;
    int Binsearch(char *a,int n,const char &x)	//二分查找,前提查找序列是有序排列
    {
    	int l=0,r=n-1,mid;			//数组下标从0开始
    	while(l<=r)
    	{
    		mid=(l+r)/2;
    		if(a[mid]==x)
    			return mid;
    		if(a[mid]<x)			//在右半区间查找
    			l=mid+1;
    		else 
    			r=mid-1;			//在左半区间查找
    	}
    	return -1;
    }
    
    int Binsearch_Recursion(char *a, int l, int r,const char &x)	
    {
    	int mid;			//数组下标从0开始
    		mid=(l+r)/2;
    		if(a[mid]==x)
    			return mid;
    		if(a[mid]<x)			//在右半区间查找
    			return Binsearch_Recursion(a,mid+1,r,x);
    		else					//在左半区间查找
    			return Binsearch_Recursion(a,l,mid-1,x);			
    		if (l>=r)
    		return -1;
    }
    int main()
    {
    	char a[8]={'a','b','c','f','g','j','o','w'};	
    	char c='g';
    	int x;
    
    	cout<<"数组序列_:";
    	for (int i = 0; i < 8; i++)
    	{
    		cout<<a[i]<<" ";
    	}
    	x=Binsearch(a,7,c);
    	cout<<"\n非递归算法 "<<c<<" 在数组中的位置为:"<<x<<endl;
    
    	c='w';
    	x=Binsearch_Recursion(a,0,7,c);
    	cout<<"　递归算法 "<<c<<" 在数组中的位置为:"<<x<<endl;
    
    }

可以看出,每次比较搜索数组都会减少一半.最好情况就是mid即为x,不用说时间复杂度为o(1)

假设n为8  折半剩下4 再折半剩下2 再折半剩下1 即 2^3= 8

最坏的情况下,时间复杂度为 log2n

四.执行结果:

![Image 1][]![20151220125552469][]

[Image 1]: 
[20151220125552469]: /images/20220731/63941fd82fa549069f427cdb9c95c82f.png