二分查找

二分查找，顾名思义，就是把一段数字 掰成两半 分成两半，一半一半的去搜索答案，速度很快，是一种很实用的算法

概念

想象一下，你在玩猜数字游戏。在不知道对方数字的情况下，你要如何更快的猜到数字？

如图，狡猾的小拨鼠想了一个数65，让你来猜。于是，聪明的你想到一半一半缩小范围。

首先，你猜了50，小拨鼠告诉你太小了，要大一点

于是，你就取了 50 和 100 的平均数---75，小拨鼠说太大了，要小点

然后，你就取了 50 和 75 的平均数---62，小拨鼠说太小了，要大点（因为我们是模拟C++整数型运算，所有向下取整）

接着，你就取了 62 和 75 的平均数---68，小拨鼠说太大了，要小点

最后，你取了 62 和 68 的平均数---65，小拨鼠说你猜中了！

于是，聪明的你就在小拨鼠的帮助下发明了二分查找

可以看到，1-100的数，我们只有了5次就猜出来了，非常快。

在最坏情况下，1-100的数，我们要7次才能才出来，聪明的你于是发现二分查找的时间复杂度为O（log n）

O（log n） 是什么概念呢？

1000的log仅为10

10000的log仅为14

100000的log仅为17

1000000的log仅为20

10000000的log仅为24

100000000的log仅为27

1000000000的log仅为30

10000000000的log仅为34

感受到二分查找的快速了吗？

实现

既然要实现代码，我们就不得不提一样东西---区间

更复杂的讲义

二分法的前提是：有序序列或者答案值区间是有序的

二分查找的写法按照区间设置的不同有三种写法，它们最大的不同点是每次缩小范围的时候L或R的赋值不同，以及最后答案所在位置不同。

一、1型，区间为一闭一开(L,R]或[L,R)：

代码标志行：while(R-L>1)

（1）【1型】最大值最小类型的前开后闭区间写法：

//求最大值最小，前开后闭区间(L,R]
	int L,R,M;
	L=amin-1,R=amax+1;//答案区间范围(L,R],L是答案的下限-1，R是答案的上限+1；
	//注意区间范围宁可过大，也不要过小
	//L是开区间所以需要-1，R虽然是闭区间但是为了验证找不到答案的情况范围也需要扩大1
	while(R-L>1){//只要(L,R]区间超过1个数，继续二分查找 
		M=L+(R-L)/2;//二分，等价于=(r+l)/2，这样写防止r+l爆int范围 
		if(check(M)){//如果M是可行的答案 
			//ans=M;//可不写 
			R=M;//缩小R,由于(L,R],R表示可能是答案，所以这里不需要M-1 
		}else{//否则M不是答案 
			L=M;//缩小L，由于(L,R],L本身不是答案，所以不需要M+1; 
		}
	}
	if(R!=amax+1)//最后只要R有移动过，那么找到答案 
		cout<<R;//最后停止在区间(L,R]即(ans-1,ans]; 
	else//如果R未移动过，就是答案不在(L,R]范围内 
		cout<<"No answer";//最后停止在区间(amax,amax+1]; 
	//这种写法答案可以为：L+1==R==ans
</p>

（2）【1型】最小值最大类型的前闭后开区间写法：

	//求最小值最大，前闭后开区间[L,R) 
	int L,R,M;
	L=amin-1,R=amax+1;
	while(R-L>1){//[)
		M=L+(R-L)/2;
		if(check(M)){
			//ans=M;//可不写 
			L=M;
		}else{
			R=M;
		}
	}
	if(L!=amin-1)
		cout<<L;//[L,R)即[ans,ans+1)
	else
		cout<<"No answer";
	//这种写法答案可以为：L==R-1==ans

2、0型，区间为闭合区间[L,R]

代码标志行：while(L<R) //while(R-L>0)

（1）【0型】最大值最小类型的前闭后闭区间写法：

//求最大值最小，前闭后闭区间[L,R]
	int L,R,M,ans;
	L=amin,R=amax+1;
	while(L<R){//[],即 R-L>0
		M=L+(R-L)/2;
		if(check(M)){
			ans=m;//可不写 
			R=M;
		}else{
			L=M+1;
		}
	}
	if(R!=amax+1)
		cout<<R;//[L,R],L==R==ans
	else
		cout<<"No answer";	
	//这种写法答案可以为：L==R==ans

（2）【0型】最小值最大类型的前闭后闭区间写法：

	//求最小值最大，前闭后闭区间[L,R] 
	int L,R,M,ans;
	L=amin-1,R=amax;
	while(L<R){//[],即 R-L>0
		M=L+(R-L)/2+1;//注意这里M=(L+R)/2+1; 否则while死循环
		if(check(M)){
			ans=m;//可不写 
			L=M;
		}else{
			R=M-1;
		}
	}
	if(L!=amin-1)
		cout<<L;//[L,R],L==R==ans
	else
		cout<<"No answer";
	//这种写法答案可以为：L==R==ans

3、-1型，区间为闭合区间[L,R]

代码标志行：while(L<=R) //while(R-L>-1)

（1）【-1型】最大值最小类型的前闭后闭区间写法：

	//求最大值最小，前闭后闭区间[L,R]
	int L,R,M,ans;
	L=amin,R=amax+1;
	while(L<=R){//][,即 R-L>-1 或 R-L>=0 
		M=L+(R-L)/2;
		if(check(M)){
			ans=m;//可不写,但是一般会用ans定位答案 
			R=M-1;
		}else{
			L=M+1;
		}
	}
	if(R!=amax+1)
		cout<<ans;//[R,L],L和R错位 ],[ 。
	else
		cout<<"No answer";		
	//这种写法答案可以为：ans==L==R+1

（2）【-1型】最小值最大类型的前闭后闭区间写法：

	//求最小值最大，前闭后闭区间[L,R] 
	int L,R,M,ans;
	L=amin-1,R=amax;
	while(L<=R){//][,即 R-L>-1 或 R-L>=0 
		M=L+(R-L)/2;//注意这里M不需要+1，因为L=M+1不会造成while死循环
		if(check(M)){
			ans=m;//可不写,但是一般会用ans定位答案
			L=M+1;
		}else{
			R=M-1;
		}
	}
	if(L!=amin-1)
		cout<<ans;//[R,L],L和R错位 ],[ 
	else
		cout<<"No answer";
	//这种写法答案可以为：ans==R==L-1

以上三种写法“1型”代码最简单，所以推荐使用“1型”，但是大部分初赛题目，都会出代码较复杂的“0型”和“-1型”，所以上述三种写法都要掌握。

另外关于区间L,R的初始值设定宁可超过，不可不够

如果无法分析范围区间的时候，可以直接设置为题目给的数据范围的最大范围区间即可

前面的那个讲义是dxd写的最大值最小和最小值最大的情况，比较难，我们不予理会

好吧，说人话就是二分查找中的区间有三种类型

1.前开后闭

2.前闭后开

3.前闭后闭

接下来讲解一下简单二分查找的代码原理

就拿最简单的前开后闭型来说

我们现在要在1-10内查找数字6

按照二分查找，我们先找5

很显然，5不是答案

因为 5 < 6 ，所以我们就把左指针挪到5，来缩小范围

接下来，我们就查找5-10的平均数---7

7仍然不是答案

因为 7 > 6 ，所以我们就把右指针挪到7，来缩小范围

最后，我们查找5-7的平均数---6

得到6就是答案，输出右指针

这就是简单二分的过程

其他区间状态也是同一个道理

至于开闭区间详细讲解，就看扩展讲义

扩展讲义

二分法的前提是：有序序列或者答案值区间是有序的

二分查找的写法按照区间设置的不同有三种写法，它们最大的不同点是每次缩小范围的时候L或R的赋值不同，以及最后答案所在位置不同。

一、1型，区间为一闭一开(L,R]或[L,R)：

代码标志行：while(R-L>1)

（1）【1型】最大值最小类型的前开后闭区间写法：

//求最大值最小，前开后闭区间(L,R]
	int L,R,M;
	L=amin-1,R=amax+1;//答案区间范围(L,R],L是答案的下限-1，R是答案的上限+1；
	//注意区间范围宁可过大，也不要过小
	//L是开区间所以需要-1，R虽然是闭区间但是为了验证找不到答案的情况范围也需要扩大1
	while(R-L>1){//只要(L,R]区间超过1个数，继续二分查找 
		M=L+(R-L)/2;//二分，等价于=(r+l)/2，这样写防止r+l爆int范围 
		if(check(M)){//如果M是可行的答案 
			//ans=M;//可不写 
			R=M;//缩小R,由于(L,R],R表示可能是答案，所以这里不需要M-1 
		}else{//否则M不是答案 
			L=M;//缩小L，由于(L,R],L本身不是答案，所以不需要M+1; 
		}
	}
	if(R!=amax+1)//最后只要R有移动过，那么找到答案 
		cout<<R;//最后停止在区间(L,R]即(ans-1,ans]; 
	else//如果R未移动过，就是答案不在(L,R]范围内 
		cout<<"No answer";//最后停止在区间(amax,amax+1]; 
	//这种写法答案可以为：L+1==R==ans
</p>

（2）【1型】最小值最大类型的前闭后开区间写法：

	//求最小值最大，前闭后开区间[L,R) 
	int L,R,M;
	L=amin-1,R=amax+1;
	while(R-L>1){//[)
		M=L+(R-L)/2;
		if(check(M)){
			//ans=M;//可不写 
			L=M;
		}else{
			R=M;
		}
	}
	if(L!=amin-1)
		cout<<L;//[L,R)即[ans,ans+1)
	else
		cout<<"No answer";
	//这种写法答案可以为：L==R-1==ans

2、0型，区间为闭合区间[L,R]

代码标志行：while(L<R) //while(R-L>0)

（1）【0型】最大值最小类型的前闭后闭区间写法：

//求最大值最小，前闭后闭区间[L,R]
	int L,R,M,ans;
	L=amin,R=amax+1;
	while(L<R){//[],即 R-L>0
		M=L+(R-L)/2;
		if(check(M)){
			ans=m;//可不写 
			R=M;
		}else{
			L=M+1;
		}
	}
	if(R!=amax+1)
		cout<<R;//[L,R],L==R==ans
	else
		cout<<"No answer";	
	//这种写法答案可以为：L==R==ans

（2）【0型】最小值最大类型的前闭后闭区间写法：

	//求最小值最大，前闭后闭区间[L,R] 
	int L,R,M,ans;
	L=amin-1,R=amax;
	while(L<R){//[],即 R-L>0
		M=L+(R-L)/2+1;//注意这里M=(L+R)/2+1; 否则while死循环
		if(check(M)){
			ans=m;//可不写 
			L=M;
		}else{
			R=M-1;
		}
	}
	if(L!=amin-1)
		cout<<L;//[L,R],L==R==ans
	else
		cout<<"No answer";
	//这种写法答案可以为：L==R==ans

3、-1型，区间为闭合区间[L,R]

代码标志行：while(L<=R) //while(R-L>-1)

（1）【-1型】最大值最小类型的前闭后闭区间写法：

	//求最大值最小，前闭后闭区间[L,R]
	int L,R,M,ans;
	L=amin,R=amax+1;
	while(L<=R){//][,即 R-L>-1 或 R-L>=0 
		M=L+(R-L)/2;
		if(check(M)){
			ans=m;//可不写,但是一般会用ans定位答案 
			R=M-1;
		}else{
			L=M+1;
		}
	}
	if(R!=amax+1)
		cout<<ans;//[R,L],L和R错位 ],[ 。
	else
		cout<<"No answer";		
	//这种写法答案可以为：ans==L==R+1

（2）【-1型】最小值最大类型的前闭后闭区间写法：

	//求最小值最大，前闭后闭区间[L,R] 
	int L,R,M,ans;
	L=amin-1,R=amax;
	while(L<=R){//][,即 R-L>-1 或 R-L>=0 
		M=L+(R-L)/2;//注意这里M不需要+1，因为L=M+1不会造成while死循环
		if(check(M)){
			ans=m;//可不写,但是一般会用ans定位答案
			L=M+1;
		}else{
			R=M-1;
		}
	}
	if(L!=amin-1)
		cout<<ans;//[R,L],L和R错位 ],[ 
	else
		cout<<"No answer";
	//这种写法答案可以为：ans==R==L-1

以上三种写法“1型”代码最简单，所以推荐使用“1型”，但是大部分初赛题目，都会出代码较复杂的“0型”和“-1型”，所以上述三种写法都要掌握。

另外关于区间L,R的初始值设定宁可超过，不可不够

如果无法分析范围区间的时候，可以直接设置为题目给的数据范围的最大范围区间即可

代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	//前开后闭区间(L,R]，L是左指针，R是右指针 
	int L,R,M;
	L=amin-1,R=amax+1;//答案区间范围(L,R],L是答案的下限-1，R是答案的上限+1；
	//注意区间范围宁可过大，也不要过小
	//L是开区间所以需要-1，R虽然是闭区间但是为了验证找不到答案的情况范围也需要扩大1
	while(R-L>1){//只要(L,R]区间超过1个数，继续二分查找 
		mid=L+(R-L)/2;//二分查找 ，mid：求两数平均数 
		if(/*mid和ans关系式*/){//如果mid是可行的答案 
			//其他
			R=mid;//缩小R
		}else{//否则mid不是答案 
			L=mid;//缩小L
		}
	}
	if(R!=amax+1)//最后只要R有移动过，那么找到答案 
		cout<<R;//最后停止在区间(L,R]即(ans-1,ans]; 
	else//如果R未移动过，就是答案不在(L,R]范围内 
		cout<<"No answer";//最后停止在区间(amax,amax+1]; 
	//这种写法答案可以为：L+1==R==ans
	return 0;
}

题目

网址

二分查找1（最大值最小）查找>x的数

题目描述

在单调不下降序列A中查找第一个大于x的数。（即>x的数中最小的一个数）

输入输出

输入

第一行两个数N和x 第二行N个递增序列

输出

第一行：找到符合条件的数的序列 第二行：输出该数值

如果没找到符合条件的数则输出“Not found!”

样例

10 66
10 25 52 62 66 66 66 85 87 95

8
85

10 99
10 25 52 62 66 66 66 85 87 95

Not found!

数据范围

1<=N<=2000000

这很明显是一道经典的二分查找题目

方法一

暴力裸搜

AC

#include <bits/stdc++.h>
using namespace std;
long long a[10000005];
int main(){
   	long long n,x;
   	cin>>n>>x;
   	for(int i=1;i<=n;i++){
   		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
   		if(a[i]>x){
   			cout<<i<<endl<<a[i];
   			return 0;
		}
	}
	cout<<"Not found!";
    return 0;
}

方法二

二分查找

AC

#include <bits/stdc++.h>
using namespace std;
long long a[10000005];
int main(){
   	long long n,x;
   	cin>>n>>x;
   	for(int i=1;i<=n;i++){
   		cin>>a[i];
	}
	int s=0,e=n+1;
	while(e-s>1){
		int mid=s+(e-s)/2;
		if(a[mid]>x){
			e=mid;
		}else{
			s=mid;
		}
	}
	if(e==n+1){
		cout<<"Not found!";
		return 0;
	}
	cout<<e<<endl<<a[e];
    return 0;
}

函数

大概讲一下二分查找的函数

binary_search 是否存在等于 value 的元素 bool 只需 判断存在性

lower_bound 第一个 >= value 的位置 迭代器 查找插入 点、查找下界

upper_bound 第一个 > value 的位置 迭代器 查找上界

equal_range 同时返回 lower_bound 和 upper_bound

pair<迭代器, 迭代器> 获取等于 value 的全部范围

函数不是很重要，了解一下即可

参考：

关于二分答案搜索三种写法的分析 · 文章

二分查找讲义1

二分查找讲义2

题目网址

二分查找函数（gf25030的博客）

本blog的图为本人手画

本模板为本人手写

本blog由本人 手搓 手写

什么！你居然看到大结局了！

  1. Language
  2. 兼容模式
  3. 主题
  2. 粤ICP备2022142345号-1
  4. Worker 0, 15ms
  5. Powered by Hydro v5.0.0-beta.18 Community