样例过,测全WA,求调教

P2249 【深基13.例1】查找

Simon3_14 @ 2023-10-27 19:36:49

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int n, m, x, y;
    cin >> n >> m;
    vector<int>a;
    vector<int>b;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        a.push_back(x);
    }//第一组数

    for (int i = 0; i < m; i++)
    {
        cin >> y;
        b.push_back(y);
    }//第二组数

    for (int i = 0; i < m; i++)
    {
        int p = lower_bound(a.begin(),a.end(), b[i]) - a.begin();//二分查找

        if(b[i]!=a[p])//判断输出,但这里没搞明白...
            cout << "-1";
        else
            cout<<p+1<<" ";
    }
    return 0;
}

我想请教一下该怎么改?


by peterJr @ 2023-10-27 19:56:07

查找算法(请翻阅教材)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define INF 1000007
int n, m, a[INF], b[INF], mid, l, r;
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++){
        cin >> b[i];
    }
    for (int i = 1; i <= m; i++){
        l = 1;
        r = n;
        while (l < r){
            mid = (l + r) / 2;
            if (b[i] > a[mid]){
                l = mid + 1;
            }   else{
                r = mid;
            }
        }
        if (a[l] == b[i]){
            cout << l << ' ';
        }
        else
        {
            cout << -1 << ' ';
        }
    }
    return 0;
}

|