零分求助

heyZZZ @ 2024-01-30 09:37:02

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],x,l,r,flag=0; 
int main() {
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=0;i<m;i++){
        cin>>x;
        l=1,r=n;
        while(l<r){
            int mid=(l+r)/2;
            if(a[mid]>=x) r=mid-1;
            if(a[mid]<x) l=mid+1;
        }
        if(a[l]==x) printf("%d ",l);
        else printf("-1 ");
    }
    return 0;
}

by danlao @ 2024-01-30 09:44:25

@heyz l+r有可能爆int，你可以开long long或改成l+(r-l)/2

by jesse1216 @ 2024-01-30 09:51:33

二分写错了吧。

你的 l,r 到底代表什么？

这么写试试：

int l = 1, r = n, mid, ans;
while (l <= r) {
  mid = (l + r) >> 1;
  if (a[mid] > x) r = mid - 1;
  else if (a[mid] < x) l = mid + 1;
  else {
    ans = mid;
    break;
  }
}
cout << ans << ' ';

另外 l+r\le2n 不可能爆 int。

by jesse1216 @ 2024-01-30 09:51:49

@heyz

by heyZZZ @ 2024-01-30 09:59:15

AC

谢谢！！！！

by wydwydwydwyd @ 2024-02-04 14:01:49

@heyz 把你的r=mid-1改成r=mid

by wydwydwydwyd @ 2024-02-04 14:02:29

如果两个数相同的时候不一定这个数不算