二分查找 理论 例题

递归代码

int binary_search(int arr[],int left,int right,int key){
	if (left>right){//区间无效
		return -1;
	}
	int mid=left+(right-left)/2; //直接平均可能会溢出
	if(arr[mid]==key){
		return mid;
	}else if(key>arr[mid]){
		return binary_search(arr,mid+1,right,key); //右半区间继续查找
	}
	else{
		return binary_search(arr,left,mid-1,key); //左半区间继续查找
	}
}

 循环代码

//代码中 arr 表示数组，left 表示区间左边界， right 表示区间右边界，mid 表示中间位置
int binary_search(int arr[],int left,int right,int key){
	int ret=-1;//未搜索到数据返回-1
	int mid;//中间位置
	while(left<=right){//只要区间有效就继续
		mid=left+(right-left)/2; //直接平均可能会溢出
		if(arr[mid]==key){
			ret=mid;//找到
			break; 
		}
		else if(key>arr[mid]){//右半区间继续查找
			left=mid+1;
		}
		else{
			right=mid-1; //左半区间继续查找
		}
	}
	return ret; // 返回结果
}

1

#include<iostream>
using namespace std;
int main(){
	int a[5]={1,2,2,3,4};
	int n;
	cin>>n;
	int l=0,r=4;
	int m;
	while(l<=r){
		m=l+(r-l)/2;
		if(a[m]>=n){
			r=m-1;
		}else{
			l=m+1;
		}
		if(a[l]==n){
			cout<<l;
			return 0;
		}
		
	}
	cout<<-1;
}

2

#include<iostream>
using namespace std;
int main(){
	int a[5]={1,2,2,3,4};
	int n;
	cin>>n;
	int l=0,r=4;
	int m;
	while(l<=r){
		m=l+(r-l)/2;
		if(a[m]>n){
			r=m-1;
		}else{
			l=m+1;
		}
		if(a[r]==n){
			cout<<r;
			return 0;
		}
	}
	cout<<-1;
}

3

#include<iostream>
using namespace std;
int main(){
	int a[9]={1,4,5,8,10,10,12,13,15};
	int n;
	cin>>n;
	int l=0,r=8;
	int m;
	while(l<=r){
		m=l+(r-l)/2;
		if(a[m]>=n){
			r=m-1;
		}else{
			l=m+1;
		}
		if(a[l]>=n){
			cout<<l;
			return 0;
		}
	}
	cout<<-1;
}

4

#include<iostream>
using namespace std;
int main(){
	int a[9]={1,4,5,8,10,10,12,13,15};
	int n;
	cin>>n;
	int l=0,r=8;
	int m;
	while(l<=r){
		m=l+(r-l)/2;
		if(a[m]>n){
			r=m-1;
		}else{
			l=m+1;
		}
		if(a[r]<=n){
			cout<<r;
			return 0;
		}
	}
	cout<<-1;
}