P2249 【深基13.例1】查找

P2249 【深基13.例1】查找

P2249 【深基13.例1】查找

题意

输入n 个不超过10的9次方的单调不减的（就是后面的数字不小于前面的数字）非负整数a1，a2，a3…然后进行
m 次询问。对于每次询问，给出一个整数q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出−1。
第一行 2 个整数n 和 m，表示数字个数和询问次数。
第二行 n 个整数，表示这些待查询的数字。
第三行 m 个整数，表示询问这些数字的编号，从 1 开始编号。

坑点

1. 无，挺简单的。

算法一：循环+判断

时间复杂度

• 输出大小: 1.83249378204346 MiB
• 编译时间: 0.58s

代码

 #include<iostream>
#include<stdio.h>
using namespace std;
int main()
{int n,q;cin>>n>>q;int a[n],x;for(int i=1;i<=n;i++){cin>>a[i];}while(q--){cin>>x;int l=1,r=n;while(l<r){int mid=l+r>>1;//寻找中间值，往右移一位。 if(a[mid]>=x) r=mid; else l=mid+1;}if(a[l]!=x){cout<<-1<<" ";continue;}else{cout<<l<<" ";}}return 0;
} 

总结

循环+判断，主要是题目理解意思。