A8022.查找:思路+题解

*经典的二分查找题目（板子题）
如果出现思路方面的不理解，建议看
二分查找相关知识点：https://www.acgo.cn/discuss/study/36311

接下来先放伪代码

#include<bits/stdc++.h>//万能头
using namespace std;
int a[105];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];//输入
	int x;
	cin>>x;
	int left=  ;
	int right=   ;
    //二分查找的左端点和右端点有很多种写法，这里是一种（比较简单且容易理解的）左闭右闭区间[]，也就是将数据范围分为三个部分
    //[left,mid-1][mid][mid+1,right]
	int ans=  ;
    //ans(answer)记录答案，初始值按照题目要求改为-1
	while(            ){//循环条件：当左端点没有碰到右端点时
		int mid=(left+right)/2;
		if(a[mid]==x){
            //如果找到要求值，记录下来，退出循环
		}else if(a[mid]<x){ 
            //[left,mid-1][mid][mid+1,(x,)right](发现x在第三个部分，将左端点转移到mid+1,在[mid+1,right]之间查找)
		}else if(a[mid]>x){
             //[left,(x,)mid-1][mid][mid+1,right](发现x在第一个部分，将右端点转移到mid-1,在[left,mid-1]之间查找)
		}
	}
	cout<<ans;
}

正经代码：

#include<bits/stdc++.h>//万能头
using namespace std;
int a[105];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];//输入
	int x;
	cin>>x;
	int left=1;
	int right=n;
    //二分查找的左端点和右端点有很多种写法，这里是一种（比较简单且容易理解的）左闭右闭区间[]，也就是将数据范围分为三个部分
    //[left,mid-1][mid][mid+1,right]
	int ans=-1;
    //ans(answer)记录答案，初始值按照题目要求改为-1
	while(left<=right){
		int mid=(left+right)/2;
		if(a[mid]==x){
            //如果找到要求值，记录下来，退出循环
			ans=mid;
			break;
		}else if(a[mid]<x){ 
            //[left,mid-1][mid][mid+1,(x,)right](发现x在第三个部分，将左端点转移到mid+1,在[mid+1,right]之间查找)
			left=mid+1;
		}else if(a[mid]>x){
			right=mid-1;
             //[left,(x,)mid-1][mid][mid+1,right](发现x在第一个部分，将右端点转移到mid-1,在[left,mid-1]之间查找)
		}
	}
	cout<<ans;
}

STL版本（参见二分查找相关知识点）：

#include<bits/stdc++.h>
using namespace std;
int a[1000006];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		if(a[lower_bound(a+1,a+1+n,x)-a]==x){
			cout<<lower_bound(a+1,a+1+n,x)-a<<" ";
		}else cout<<-1<<" ";
	}
}