#565. 查找之大编号
题目描述
输入 𝑛(𝑛≤106)n(n≤106) 个不超过 109109 的单调不减的（就是后面的数字不小于前面的数字）非负整数 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an，然后进行 𝑚(𝑚≤105)m(m≤105) 次询问。对于每次询问，给出一个整数 𝑞(𝑞≤109)q(q≤109) ，要求输出这个数字在序列中最后一次出现的编号，如果没有找到的话输出 −1−1 。
输入
第一行 22 个整数 𝑛n 和 𝑚m ，表示数字个数和询问次数。
第二行 𝑛n 个整数，表示这些待查询的数字。
第三行 𝑚m 个整数，表示询问这些数字的编号，从 11 开始编号。
输出
𝑚m 个整数表示答案。
样例
输入数据 1
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
Copy
输出数据 1
1 4 -1
Copy
提示
请用 scanf。用 cin 会超时。
#include<bits/stdc++.h>
using namespace std;
int a[1000010],n,m;
//手写二分查找函数
int binatySearch(int num){int left = 1,right = n+1;//左闭右开区间 while(left < right){int mid = left + (right - left)/2;if(num == a[mid]) left = mid + 1;if(num < a[mid]) right = mid;if(num > a[mid]) left = mid+1;}if(a[right - 1] == num)return right - 1;return -1;
}
int main(){cin >> n >> m;for(int i = 1; i <= n; i++)scanf("%d",&a[i]);while(m--){int num;scanf("%d", &num);printf("%d ",binatySearch(num));}return 0;
}