【深基13.例1】查找

题目描述

输入 \(n\) 个不超过 \(10^9\) 的单调不减的（就是后面的数字不小于前面的数字）非负整数 \(a_1,a_2,\dots,a_{n}\)，然后进行 \(m\) 次询问。对于每次询问，给出一个整数 \(q\)，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 \(-1\) 。

输入格式

第一行 \(2\) 个整数 \(n\) 和 \(m\)，表示数字个数和询问次数。

第二行 \(n\) 个整数，表示这些待查询的数字。

第三行 \(m\) 个整数，表示询问这些数字的编号，从 \(1\) 开始编号。

输出格式

输出一行，\(m\) 个整数，以空格隔开，表示答案。

样例 #1

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出 #1

1 2 -1

提示

数据保证，\(1 \leq n \leq 10^6\)，\(0 \leq a_i,q \leq 10^9\)，\(1 \leq m \leq 10^5\)

本题输入输出量较大，请使用较快的 IO 方式。

代码

二分

#include <bits/stdc++.h>
using namespace std;
int n,m,a[1000001],t[100001]; 
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		cin >> a[i];
	} 
	for(int i=1;i<=m;i++) 
	{
		cin >> t[i];
	}
	for(int i=1;i<=m;i++)
	{
		int l=1,r=n;
		while(l<r)
		{
			int mid=(l+r)/2;
			if(a[mid]>=t[i])
			{
				r=mid;
			} 
			else{
				l=mid+1;
			} 
		}
		if(a[r]==t[i]) 
		{
			cout << r << ' ';
		}
		else{
			cout << -1 << ' ';
		}
	}
	return 0;
}