求教

P2249 【深基13.例1】查找

He_4002602 @ 2023-07-12 11:17:10

为什么第一段全WA 第二段把mid改成l就AC了 第一段

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    vector<int> a(n);

    for(int i=0;i<n;++i){
        cin>>a[i];
    }

    int t,l,r,mid;
    while(m--){
        cin>>t;
        l=0;r=n-1;
        while(l<=r){
            mid=(r+l)/2;
            if(a[mid]>=t)r=mid-1;
            else l=mid+1;
        }
        if(a[mid]==t)
        cout<<mid+1<<" ";
        else cout<<-1<<" ";
    }
    return 0;
}

第二段

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    vector<int> a(n);

    for(int i=0;i<n;++i){
        cin>>a[i];
    }

    int t,l,r,mid;
    while(m--){
        cin>>t;
        l=0;r=n-1;
        while(l<=r){
            mid=(r+l)/2;
            if(a[mid]>=t)r=mid-1;
            else l=mid+1;
        }
        if(a[l]==t)
        cout<<l+1<<" ";//只有这两行不一样
        else cout<<-1<<" ";
    }
    return 0;
}

by Gohidg @ 2023-07-12 11:23:17

你的mid有一种情况是找到了,但是你的r会继续-1,然后越过l,所以真正答案是l+1,你可以试试在while(l<=r)这个循环里特判,如果a[mid]==t,就是找到了就输出mid,打个标记,接着跳出整个循环,结束后判断是否被标记,没有标记就输出-1


by Gohidg @ 2023-07-12 11:24:14

@He_4002602 在if else前面判断,或者增加一个else


by He_4002602 @ 2023-07-12 11:27:39

@_I_qwqI 哦哦我好像知道了,谢谢大佬


by Gohidg @ 2023-07-12 11:35:46

我不是dalao,Gohlg是dalao


by Gohidg @ 2023-07-12 11:36:11

打错了 是Gohldg


by Gohidg @ 2023-07-12 11:36:43

@Gohldg


by Gohldg @ 2023-07-12 11:38:21

???什么鬼,滚啊


|