【二分查找详细解析】& 【图解】& 例题【洛谷P2249 【深基13.例1】查找】

二分查找的基础解释

二分的时间复杂度为$O(logn)$，进行二分查找的序列必须满足单调性

我们可以先定义两个值 $l,r$ ，来表示查找到的左端点 $l$，和右端点 $r$

原理与代码模板如下图↓：

while(l<r){
	int mid=(l+r)>>1;
	if(check(mid)) l=mid+1;
	else r=mid;
}

定义一个样例：

5
1 4 8 9 20

我们定义要查找的数为 $x$ (保证 $x$ 一定存在)，$check(mid)$的条件为，$mid\le x$，则 $check(mid)=true$

l   r  mid
1   5   3
4   5   4

每一次，如果 $check(mid)$ 成立，则抛弃小于等于 $mid$ 的部分

同理，如果 $check(mid)$ 不成立，则抛弃大于 $mid$ 的部分

例题【洛谷P2249 【深基13.例1】查找】

题目链接:洛谷P2249 【深基13.例1】查找

题目大意：给出n个数，m个询问，每个询问包含一个整数q，输出n中最先出现的q的编号（这n个数满足单调性）

code↓

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+50;//定义数组边界
long long n,a[maxn]={},m,q;//n为元素个数,m为询问个数
long long check(long long mid){//检查mid是否满足条件
	if(a[mid]>=q) return 1;//如果这个数比它大，则满足条件
	else return 0;//否则不满足条件
}
int main(){
	ios::sync_with_stdio(false);//输入优化
	cin.tie(0),cout.tie(0);//输入优化
	cin>>n>>m;//输入元素个数，与询问个数
	for(int i=1;i<=n;i++) cin>>a[i];//输入数组的值
	for(int i=1;i<=m;i++){
		cin>>q;//q便是我们需要查找的数
		long long l=1,r=n;//定义初始值
		while(l<r){
			long long mid=(l+r)>>1;//mid就是这个区间的一半,>>x代表/2^{x}
			if(check(mid)) r=mid;//r的位置保持不变
			else l=mid+1;//如果比它小，则舍弃左边的值
		}
		if(a[l]==q) cout<<l<<" ";//如果找到了这个值，则输出它的编号
		else cout<<-1<<" ";//如果没找到这个数，则输出-1
	}
	return 0;
}

此题代码已AC