【深基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 方式。
题解
刚开始还把二分的边界给初始化错了
题目求的是当前数在数组中的位置(也就是编号) 所以二分的边界应该是数组的首节点和尾节点 int l = 1, r = n;
一定不要多开 要是查的当前元素是0的话 直接查到多开的地址上去了
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int a[N];
void solve()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
while (m -- )
{
int k;
scanf("%d", &k);
int l = 1, r = n; //左右边界是当前数组的起始位置和终止位置编号
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] >= k) r = mid;
else l = mid + 1;
//cout << l << " " << r << endl;
}
if (a[l] != k) printf("-1 "); //当不符合条件时
else printf("%d ", l);
}
return;
}
int main()
{
solve();
return 0;
}
stl库内lower_bound写法
int main(){
int n=read(),m=read();//读入
for(int i=1;i<=n;i++) a[i]=read();
while(m--){
int x=read();
int ans=lower_bound(a+1,a+n+1,x)-a;//二分搜,注意-a
if(x!=a[ans]) printf("-1 ");//没有,输出-1
else printf("%d ",ans);//有,输出ans
}
return 0;//华丽结束
}