2497: 【普及-】【P2249】查找
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：47
解决：12
题目描述
输入 个不超过 的单调不减的（就是后面的数字不小于前面的数字）非负整数 ，然后进行 次询问。对于每次询问，给出一个整数 ，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 。
输入
第一行 个整数 和 ，表示数字个数和询问次数。
第二行 个整数，表示这些待查询的数字。
第三行 个整数，表示询问这些数字的编号，从 开始编号。
输出
输出一行， 个整数，以空格隔开，表示答案。
样例输入 复制
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6样例输出 复制
1 2 -1 提示
数据保证，，，
本题输入输出量较大，请使用较快的 IO 方式。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000010
int a[MAXN],m,n,q;
/**
int find(int x) {
int l = 1, r = n;
while (l <= r) { //
int mid = (l+r)/2; //中间页数
if (a[mid] == x)return mid; //刚好找到需要的数字
else if (a[mid]>x) r=mid-1; //取区间的前一半
else l=mid+1; //取区间的后一半
}
return -1;
}
**/
int find(int x) {
int l = 1, r = n + 1;
while (l < r) { // 最后 l 和 r 会相等。
int mid = l + (r - l)/2;
// 有时 l+r 可能会超过 int 类型的极限（当然本例不会），这么做可以避免运算溢出。
if (a[mid] >= x)r = mid;
else l = mid + 1;
}
if(a[l] == x)return l;
else return -1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=0;i<m;++i) {
cin>>q;
cout<<find(q)<<" ";
}
return 0;
}