不理解为什么输出成了1 3 -1

P2249 【深基13.例1】查找

Yaojie_24 @ 2024-06-20 18:02:05

#include<iostream>
#define MAXN 1000010
using namespace std;
int a[MAXN] , m , n , q;
int find(int x) {
    int l = 1,r = n;
    while (l <= r) {
        int mid = (l+r)/2; 
        if (a[mid] == x) return mid;
        else if (a[mid] > x)r = mid - 1; 
        else l = mid + 1; 
    }
    return -1;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 0; i < m; ++i) {
        cin >> q;
        cout << find(q) << " ";
    }
    return 0;
}

by CC__DIAMOND @ 2024-06-20 18:09:00

注意到 l=r-1 时,如果 a[r]=va[l] \neq vr 会被更新为 l-1。这是错误的。二分不能这么写,建议查看他人的实现或者调用 lower_bound


by Yaojie_24 @ 2024-06-21 14:25:33

@CC__DIAMOND 谢谢!问题已解决~


|