xk2013 @ 2024-03-17 13:47:33
#include <cstdio>
int n, m, q, *a;
int find(int n);
int main(void)
{
scanf("%d %d", &n, &m);
a = new int[n + 1];
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
for (int i = 0; i < m; i++)
{
scanf("%d", &q);
printf("%d ", find(q));
}
return 0;
}
int find(int n)
{
int l = 1, r = n;
while (l <= r)
{
int mid = (l + r) / 2;
if (a[mid] == n)
{
return mid;
}
if (a[mid] < n)
{
l = mid + 1;
}
else if (a[mid] > n)
{
r = mid - 1;
}
}
return -1;
}
洋历克果(样例可过)。
by xk2013 @ 2024-03-17 13:48:22
@Special_Tony @zltzt @chat_jinxuan MnZn
by QBW1117 @ 2024-03-17 13:57:56
对于每次询问,给出一个整数 q,要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出 −1 。
要查的是数,不是下表 所以find函数里的n和全局的n混淆
by CuteChat @ 2024-03-17 14:02:31
find 的参数和全局 n 重名了
by quxiangyu @ 2024-03-17 14:10:07
@xk2013 @xk2013 求关注இ௰இ
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000005
#define put putchar('\n')
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define R(i,a,b) for (int i=(a);i<(b);i++)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define pa pair<int,int>
#define pb push_back
#define be begin()
#define en end()
#define ret return puts("-1"),0;
#define N 1300055
#define mod 998244353
#define int ll
using namespace std;
#define gc getchar
inline ll read(){char c=getchar();ll tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
ll sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(ll x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(ll x){wr(x);put;}inline void wri(ll x){wr(x);putchar(' ');}
inline void wrn(ll x,ll y){wri(x);wrn(y);}inline void wrn(ll a,ll b,ll c){wri(a);wrn(b,c);}
//read()读入 ,wr(x) 输出 wrn(x) 输出换行
int n,m,a[1000005];
int check(int x){
//输出这个数字在序列中第一次出现的编号,如果没有找到的话输出 -1
//我们的二分实现的是从左到右第一个>=x的数的位置
/*int l=1,r=n,ans=-1;
while (l<=r){
int mid=(l+r)/2;
if (a[mid]>=x) r=mid-1,ans=mid;//如果a[mid]>=x,那么最靠左的>=x的位置一定比mid小或者就是mid
else l=mid+1;//说明a[l]..a[mid]<x
}*/
int ans;
ans=lower_bound(a+1,a+n+1,x)-a;
if (ans==n+1) return -1;
if (a[ans]==x) return ans;
else return -1;
}
signed main(){
n=read();m=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<m;i++){
int t=read();
printf("%d ",check(t));
}
printf("%d",check(read()));
return 0;
}
by quxiangyu @ 2024-03-17 14:11:43
不用管头文件~o( =∩ω∩= )m
by xk2013 @ 2024-03-17 14:48:20
@quxiangyu 求壶关இ௰இ
by quxiangyu @ 2024-03-17 15:04:21
@xk2013 OK
by wnsndg @ 2024-03-17 20:48:44
求关注:)
//P2249 【深基13.例1】查找
#include<iostream>
using namespace std;
int n,m,q,a[1000005];
int find(int x){ //二分查找函数
int l=1,r=n; //确定左右端点,左端点为第一个,右端点为最后一个
while(l<r){
int mid=l+(r-l)/2; //确定中点
if(a[mid]>=x) r=mid; //如果当前比答案大,那就要搜索前半部分,右端点为中点减
else l=mid+1; //否则搜索后半部分,左端点为中点加一
}
if(a[l]==x)return l; //因为某种不知名原因,所以只能在外面判断是否找到,找到返回左端点(或右端点)
return -1; //没找到返回-1
}
int main(){
cin>>n>>m; //读入长度与访问次数
for(int i=1;i<=n;i++)
cin>>a[i]; //读入有序数列
for(int i=1;i<=m;i++){
cin>>q; //输入访问数字
cout<<find(q)<<" "; //通过二分函数来进行查找
}
return 0; //华丽收工
}