C++二分查找

在编程中，我们经常会遇到一些问题，需要我们查找指定元素的位置。这种题可以运用很多种办法解决，但是时间复杂度普遍较高，所以今天介绍一种复杂度较低的方法，那就是二分查找。我们可以运用分治思想，将一个序列从中间拆开，分成两个部分，经过一个基准元素（一般为中间数）进行比较，比较后将不符合的区间丢掉。

我会将二分查找分为整数查找和实数查找两方面来介绍。

一.整数查找：

靠左查找：

进行查询时，尽可能找到符合条件的最靠左的值，如果切割点mid（中间数）符合条件，应保留答案，删除靠右区间，将靠左的区间继续二分，直到不可再分。

例：

题目：输入 n 个不超过 109 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1​,a2​,…,an​，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1145141];
int ask(int x){
	int l=1,r=n;
	while(l<r){
		int mid=l+r>>1;//寻找中间数mid
		if(a[mid]>=x) r=mid;//将右边部分丢掉
		else l=mid+1;//将左边部分丢掉
	}
	if(a[l]!=x) return -1;
	return l;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		cout<<ask(x)<<" ";
	}
}

靠右查找：

进行查询时，尽可能找到符合条件的最靠右的值，如果切割点mid符合条件，应保留答案，删除靠左区间，将靠右的区间继续二分，知道不可再分。
 

例：

题目：给出有 n 个元素的由小到大的序列，请你编程找出某元素最后一次出现的位置。
(n<=10^6)

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[1145141];
int ask(int x){
	int l=1,r=n;
	while(l<r){
		int mid=l+r+1>>1;//mid为中间数
		if(a[mid]<=x) l=mid;//将左边部分丢掉
		else r=mid-1;//将右边部分丢掉
	}
	if(a[l]!=x) return -1;
	return l;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int x;cin>>x;
	cout<<ask(x);
}

当然，c++也有自带的关于整数查找函数：

1.

binary_search(a+1,a+n+1,x)

作用：查找单调序列中，在指定区域内[1,n]是否存在目标值x。存在返回true,不存在返回false。

使用方法：

int k=binary_search(a+1,a+7,3); //k=1

2.

lower_bound(a+1,a+n+1,x)

作用：查找不降序列中，在指定区域内[1,n]大于苗志x的第一个元素所在地址。（靠左查找）

使用方法：

int pos=lower_bound(a+1,a+7,3)//元素位置在a+2，所以pos=5

3.

upper_bound(a+1,a+n+1,x)

作用：查找不降序列中，在指定区域内[1,n]大于目标值x的第一个元素所在地址。（这次是靠右查找）

使用方法：

int pos=upper_bound(a+1,a+n+1,x)//元素位置在a+5，所以pos=5

二.实数查找：

对于实数的二分，与整数二分主要的差异体现在以下两个方面：
1.实数不会出现因整数取整而导致的mid偏向问题。即
double mid=(l+r)/2，不用考虑会因为mid错误导致死循环。
2.实数中，两个相邻的数字间隔不一定是1，所以不能
用加减1来进行寻找。最后找到的数字也可能是相似值，所以只要满足精度即可。
一般来说如果题目要求保留k位小数，此时l,r是不一样的。我
们会把精度设置到小数点后k+2位。（k+1位会对第k位的进
位产生很大影响，k+2位相对好一点。），此时输出l或r基本
相同

总结：

二分查找它相比于快速排列具有更强的稳定性，又比暴力枚举时间复杂度更低，使我们的程序更加优化。

感谢各位大佬的阅读