二分查找炸了，救命！！！

Star_Sky_ @ 2023-12-04 18:51:23

#include <iostream>
#include <cstdio>

using namespace std;

int search(int ans , int list[] , int l , int r)
{
    int key;

    while (l <= r)
    {
        key = l+(l+r)/2;

        if (list[key] > ans)
        {
            r = key-1;
        }
        else if (list[key] < ans)
        {
            l = key+1;
        }
        else
        {
            return key;
        }
    }

    return -1;
}

int main()
{
    int n , t , tmp;
    scanf("%d%d" , &n , &t);

    int list[n];

    for (int i = 0 ; i < n ; i++)
    {
        scanf("%d" , &list[i]);
    }

    for (int i = 0 ; i < t ; i++)
    {
        scanf("%d" , &tmp);
        printf("%d\n" , search(tmp , list , 0 , n-1)-1);
    }

    return 0;
}

by So_noSlack @ 2023-12-04 19:00:55

@2023libingxuan \text{key} 变量的修改错了，应该是 \text{key=(l+r)/2}。

by PRew_ @ 2023-12-04 19:02:42

@So_noSlack 大佬看看我代码呗

by PRew_ @ 2023-12-04 19:03:40

@So_noSlack https://www.luogu.com.cn/discuss/742161

by So_noSlack @ 2023-12-04 19:07:15

并且题目不需要换行，而且你无法确定二分查找的值是不是最前的一个，建议 \text{ans} 记录值，一直搜完不要停。

没听懂的话私信我，我发你代码。

by Star_Sky_ @ 2023-12-05 13:20:42

@So_noSlack 谢谢

by So_noSlack @ 2023-12-06 10:44:17

@2023libingxuan 代码：

#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 1000005

int n, q, a[MAXN], x;

int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    while(q --) {
        cin >> x;
        int l = 1, r = n, mid, ans = -1;
        while(l <= r) {
            mid = l + ((r - l) >> 1);
            if(a[mid] >= x) r = mid - 1, ans = mid;
            else l = mid + 1;
        }
        if(a[ans] == x) cout << ans << " ";
        else cout << "-1 ";
    }
    return 0;
}

你那个代码有个问题，就是如果相同的数字过多的话会 \text{TLE}，建议你记一下我这个模板，这种比较常用。

by So_noSlack @ 2023-12-06 10:45:39

这里的 \text{mid} 计算方法可以防止爆 \text{int}，功能不变。