又是wa又是re

P2249 【深基13.例1】查找

aishiteru_mitsu_ha @ 2024-02-02 15:23:00

#include<iostream>
using namespace std;
bool no;
int n, a[100000], l = 1, h, mid, cnt;
int main() {
    cin >> n >> cnt;
    h = n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= cnt; i++) {
        int m;
        l = 0;
        h = n + 1;
        cin >> m;
        while (l != h - 1) {
            mid = (l + h) / 2;
            if (a[mid] < m) {
                l = mid;
                continue;
            }
            else if (a[mid] > m) {
                h = mid;
                continue;
            }
            else {
                cout << mid << " ";
                no = true;
                break;
            }
        }
        if (no == true) {
            no = false;
            continue;
        }
        cout << -1 << " ";
    }
    return 0;
}

by _Deer_Peach_ @ 2024-02-02 15:31:10

可以用lower_bound()\ lower_bound()的用法


by _Deer_Peach_ @ 2024-02-02 15:33:10

@3247535661 lower_bound(first,last,val) "first"是数组起始位置 "last"是数组终止位置 "val"是寻找的目标值


by aishiteru_mitsu_ha @ 2024-02-02 15:33:14

#include<iostream>
using namespace std;
bool no;
int n, a[100000], l = 1, h, mid, cnt;
int main() {
    cin >> n >> cnt;
    h = n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= cnt; i++) {
        int m;
        l = 0;
        h = n + 1;
        cin >> m;
        while (l != h - 1) {
            mid = (l + h) / 2;
            if (a[mid] < m) {
                l = mid;
                continue;
            }
            else {
                h = mid;
                continue;
            }
        }
        if (a[mid] == m) {
            cout << mid << " ";
        }
        else {
            cout << -1 << " ";
        }
    }
    return 0;
}

by aishiteru_mitsu_ha @ 2024-02-02 15:33:30

@3247535661 帖子打不开


by _Deer_Peach_ @ 2024-02-02 15:34:11

具体代码实现


#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int a[n],ans[m];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<m;i++){
        int x;
        cin>>x;
        int y=lower_bound(a+0,a+n,x)-a;
        if(a[y]!=x)ans[i]=-2;
        else ans[i]=y;
    }
    for(int i=0;i<m;i++)cout<<ans[i]+1<<" ";
    return 0;
}

by _Deer_Peach_ @ 2024-02-02 15:37:00

lower_bound()返回一个迭代器,指向数组中第一个不小于目标值的元素如果数组中不存在不小于的元素,则返回“last”


|