WA+Re+TLe求助

xzc_yhxr @ 2024-02-14 20:35:42

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

by SF_bee @ 2024-02-14 20:48:12

二分写错了吧

by OIerWu_829 @ 2024-02-14 21:07:55

@xzc_yhxr

给你提供一下我的二分（远古代码马蜂不好请见谅）

int q;
cin >> q;
int l = 1, r = n, ans = -1;
while (l <= r)
{
     int m = (l + r) / 2;
     if (a[m] >= q) 
     {
          r = m - 1;
          ans = m;
     }
     else l = m + 1;
}
if (ans != -1 && a[ans] == q) cout << ans << " ";
else cout << -1 << " ";

by DustyMark @ 2024-02-14 21:09:02

@xzc_yhxr 真惨，但你这while里面带 = ，咋判断逻辑写的是不是查找也不是上下限的那啥啊

by SF_bee @ 2024-02-14 21:12:12

还有，你的数组开小了，是1e6不是1e5

by frz_fw @ 2024-02-19 20:41:20

@xzc_yhxr mid 的值不应该加一

by xzc_yhxr @ 2024-02-20 10:39:15

@frz_fw WHY，有区别吗

by frz_fw @ 2024-02-20 14:16:55

@xzc_yhxr 有，加上那个1，mid的值就不对了，在你的代码里，去掉那个“+1”，再把数组开大一点，就AC了，这就是二分查找模板

by xzc_yhxr @ 2024-02-20 15:55:52

@frz_fw thx