dami826 @ 2023-09-10 14:30:26
#include<bits/stdc++.h>
using namespace std;
long long s[1000001];
int find(int left,int right,long long goal){
int mid;
while(left<right){
mid=(left+right)/2;
if(s[mid]==goal){
while(s[mid-1]==s[mid]&&mid>1){
mid--;
}
return mid;
}
if(s[mid]>goal){
right=mid;
}
else{
left=mid+1;
}
}
if(s[mid]==goal){
while(s[mid-1]==s[mid]&&mid>1){
mid--;
}
return mid;
}
return -1;
}
int main(){
long long n,m;
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
}
for(int i=1;i<=m;i++){
long long goal;
scanf("%lld",&goal);
printf("%d",find(1,n,goal));
if(i!=m){
printf(" ");
}
}
return 0;
}
by OIer_Kevin @ 2023-09-10 14:50:25
你这二分这么麻烦?
我的:
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10000000];
int BinarySearch(int x,int l,int r){
while(l<r){
int mid=(l+r)/2;
if(a[mid]>=x){
r=mid;
}
else{
l=mid+1;
}
}
if(a[l]==x){
return l;
}
return -1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
int x;
cin>>x;
cout<<BinarySearch(x,1,n)<<' ';
}
return 0;
}
建议好好学学二分
by OIer_Kevin @ 2023-09-10 14:53:44
@大米爱干饭
by dami826 @ 2023-09-10 15:02:43
@ganyudetinali 我把二分函数里那段```cpp if(s[mid]==goal)
换成left就A了