求助为什么我这个二分模板处理不了左边界

P2249 【深基13.例1】查找

thehanged @ 2024-01-27 23:38:13

一定要加上这句话才能ac

if(a[0] == q) return 1;
#include <iostream>
using namespace std;

const int N = 1e6 + 1;
int a[N];

int find_index(int q, int n){
    int l = 0, r = n - 1;
    if(a[0] == q) return 1;
    while (l + 1 != r){
        int mid = (l + r) / 2;
        if (a[mid] >= q) r = mid;
        else l = mid;
    }

    if (a[r] == q) return r + 1; 
    else return -1;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
    while(m --){
        int q;
        scanf("%d", &q);
        printf("%d ", find_index(q, n));
    }
    return 0;
}

by oyq784580 @ 2024-01-28 08:52:14

这是一个二分超级典型的错误

不知道你有没有发现，建议先回去看自己程序

你的二分循环条件

当二分到 $l=0$ 和 $r=1$ 时，你的循坏把此时 $break$ 了 而二分到 $mid=0$ 的方法只有这一个个！！！ 如果你能明白我的意思，就去改程序吧，千万不要抄题解(老年选手的忠告)

by oyq784580 @ 2024-01-28 08:53:33

#include <iostream>
using namespace std;

const int N = 1e6 + 1;
int a[N];

int find_index(int q, int n){
    int l = 0, r = n - 1;
//    if(a[0] == q) return 1;
    while (l != r){
        int mid = (l + r) / 2;
        if (a[mid] >= q) r = mid;
        else l = mid+1;
    }

    if (a[r] == q) return r + 1; 
    else return -1;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
    while(m --){
        int q;
        scanf("%d", &q);
        printf("%d ", find_index(q, n));
    }
    return 0;
}

正解

by thehanged @ 2024-01-28 13:41:48

@oyq784580 是的，感谢哥们，这个二分模板在有些场合是很好用的。说白了还是我没有理解

|