总结二分查找及其变形问题

方法一 ：递归法

 当有多个相同值时，若为相同的数为奇数，则取中间的数。若为偶数，则取中间靠左的数

#include<bits/stdc++.h>
using namespace std;
int test; 
//方法一 (递归法
//当有多个相同值时，若为相同的数为奇数，则取中间的数。
//若为偶数，则取中间靠左的数） 
int ef(int a[],int low,int high,int k){
	int mid=(low+high)/2;
	test = mid;
	if(low<=high){
		if(a[mid]>k)
			ef(a,low,high-1,k);
		if(a[mid]==k)
			return mid;
		if(a[mid]<k)
			ef(a,mid+1,high,k);
	}
	else
		return -1;
}

int main(){
	int a[100],k,res=-1;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	cin>>k;
//	res=ef(a,k,n); 
	res=ef(a,0,n,k); 	
	if(res<0){
		cout<<"It's not found!"<<endl;
	}
	else{
		cout<<"find it: "<<a[res]<<endl<<"这是第"<<test+1<<"个元素"<<endl;
//		cout<<res;
	}
	return 0;
} 

 

方法二 ：循环法

用递归时间复杂度太高，我们考虑用循环法实现二分查找。

根据上面递归的算法我们得到了二分查找的代码，但那个真的没有bug吗？不，还有很多细节需要处理，你试着想想如下问题如何解决：

①当有序数组中存在相同元素x时，如何查找左边的x ？

②当有序数组中存在相同元素x时，如何查找右边的x？

③当有序数组中存在相同元素x时，如何求x的个数？

下面我们就来解决一下如下问题。

①当有序数组中存在相同元素x时，如何查找右边的x ？

#include<bits/stdc++.h>
using namespace std;
int test; 

//方法二(重复元素查询右边最后一个元素） 
int ef(int a[],int x,int n){
	int left=0,right=n-1;
	int middle;
	while(left<right){
		middle = (left+right+1)/2;
		test=left;
		if(x>=a[middle])
			left = middle;
		else
			right = middle-1;
	}
	if(x==a[left]){
		return left;
	}else
		return -1;
	
}

int main(){
	int a[100],k,res=-1;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	cin>>k;
	res=ef(a,k,n); 
//	res=ef(a,0,n,k); 	
	if(res<0){
		cout<<"It's not found!"<<endl;
	}
	else{
		cout<<"find it: "<<a[res]<<endl<<"这是第"<<test+1<<"个元素"<<endl;
//		cout<<res;
	}
	return 0;
} 

 

②当有序数组中存在相同元素x时，如何查找左边的x？

#include<bits/stdc++.h>
using namespace std;
int test;

//方法三 (重复元素查询左边第一个元素) 
int ef(int a[],int x,int n){
	int left=0,right=n-1;
	int middle;
	while(left<right){
		middle = (left+right)/2;
		
		if(x<=a[middle])
			right = middle;
		else
			left = middle+1;
	}
	test=left;
	if(x==a[left]){
		return left;
	}else{
		return -1;
	}
}

int main(){
	int a[100],k,res=-1;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	cin>>k;
	res=ef(a,k,n); 
//	res=ef(a,0,n,k); 	
	if(res<0){
		cout<<"It's not found!"<<endl;
	}
	else{
		cout<<"find it: "<<a[res]<<endl<<"这是第"<<test+1<<"个元素"<<endl;
//		cout<<res;
	}
	return 0;
} 

 

③当有序数组中存在相同元素x时，如何求x的个数？

#include<bits/stdc++.h>
using namespace std;
int test;

//方法四 (重复元素查询重复元素的个数) 
int ef(int a[],int x,int n){
	int left=0,right=n-1;
	int middle;
	int tmpright;
	while(left<right){
		middle = (left+right+1)/2;
		test=left;
		if(x>=a[middle])
			left = middle;
		else
			right = middle-1;
	}
	tmpright=left;
	
	left=0,right=n-1;
	while(left<right){
		middle = (left+right)/2;
		
		if(x<=a[middle])
			right = middle;
		else
			left = middle+1;
	}
	test=left;
	if(x==a[left]){
		return tmpright-left+1;
	}else{
		return -1;
	}
}

int main(){
	int a[100],k,res=-1;
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	cin>>k;
	res=ef(a,k,n); 
//	res=ef(a,0,n,k); 	
	if(res<0){
		cout<<"It's not found!"<<endl;
	}
	else{
//		cout<<"find it: "<<a[res]<<endl<<"这是第"<<test+1<<"个元素"<<endl;
		cout<<"有"<<res<<"个重复元素";
	}
	return 0;
}