初学者二分 救救我啊 0WA了 不知道为什么 求调

P2249 【深基13.例1】查找

RealGzsJAY @ 2024-07-01 13:26:44

#include <iostream>
#include <vector>
using namespace std;
int n,m,am;
int find(int target,vector<int>& an){
    int l=0,r=n-1;
    while(l <= r){
        int mid = (l + r)/2;
        if(target == an[mid]) return mid;
        if(target < an[mid]){
            r = mid-1;
        }else if(target > an[mid]){
            l = mid+1;
        }
    }
    return -1;
}
int main(){
    cin>>n>>m;
    vector<int> an(n);
    for(int i=0;i<n;i++){
        cin>>an[i];
    }
    for(int i=0;i<m;i++){
        cin>>am;
        if(find(am,an) == 0){
            cout<<1<<' ';
            continue;
        }
        cout<<find(am,an)<<' ';
    }

}

我咋办啊擦


by xiaozhangawa @ 2024-07-01 13:44:27

找不到则输出 -1


by RealGzsJAY @ 2024-07-02 18:59:35

@xiaozhangawa 改了 但是还是0WA


by lix_qaq @ 2024-07-07 14:22:06

问题出在可能出现多个相同数据,所以二分找到一个后还要继续判定,不能直接return :D

#include <iostream>
#include <vector>
using namespace std;
int n,m,am;
int find(int target,vector<int>& an){
    int l=0,r=n-1;
    int ans=-1;
    while(l <= r){
        int mid = (l + r)/2;
        if(target == an[mid]){
            ans=mid+1;
            r=mid-1;
        }
        if(target < an[mid]){
            r = mid-1;
        }else if(target > an[mid]){
            l = mid+1;
        }
    }
    return ans;
}
int main(){
    cin>>n>>m;
    vector<int> an(n);
    for(int i=0;i<n;i++){
        cin>>an[i];
    }
    for(int i=0;i<m;i++){
        cin>>am;
        cout<<find(am,an)<<' ';
    }

}

by lix_qaq @ 2024-07-07 14:22:37

@RealGzsJAY 问题出在可能出现多个相同数据,所以二分找到一个后还要继续判定,不能直接return :D


|