题目描述
输入 n(n≤106) 个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a1,a2,…,an，然后进行 m(m≤105) 次询问。对于每次询问，给出一个整数 q(q≤109)，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 -1 。
输入格式
第一行 2 个整数 n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。
输出格式
m 个整数表示答案。
输入输出样例
输入 #1复制
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
输出 #1复制
1 2 -1
分析这个就是二分查找第一位，我们可以直接用函数也可以用底层代码来做。
1.引用函数
#include<bits/stdc++.h> using namespace std; const int maxn =1e6+6; int n, q; int a[maxn]; int main() { cin >> n >> q; a[0]=-1; for (int i = 1;i<=n;i++) { cin >> a[i]; } while (q--) { int x; cin >> x; int pt = lower_bound(a, a+n,x)-a;//二分查找函数 if (a[pt] == x) { cout << pt << ' '; } else { cout << -1 << ' '; } } return 0; }
2，底层代码来做
#include <iostream> #include <cstdio> using namespace std; int a[1000100],k; int bsearch(int l,int r){ while (l < r){ int mid=l+r >> 1; if (a[mid] >= k) r=mid ; else l=mid+1; } return l; } int main (){ int n,m; scanf ("%d%d",&n,&m); int i,j; for (i = 0;i < n;i++) scanf ("%d",&a[i]); while (m--){ scanf ("%d",&k); int c=bsearch(0,n-1); if (a[c] == k) printf ("%d ",c+1); else printf ("-1 "); } }
