c++ - c++ 一段代码中的二进制搜索似乎有问题

Question

我正在参加一个在线本地竞赛模拟，我在实现其中一个问题时遇到了问题。这是问题:

描述

现在是 Mole 的午餐时间。他的 friend 土拨鼠为他准备了一个很棒的午餐游戏。

Marmot 给 Mole 带来了 n 堆蠕虫，使得第 i 堆包含 ai 条蠕虫。他用连续的整数标记所有这些蠕虫:第一堆中的蠕虫被标记为数字 1 到 a1，第二堆中的蠕虫被标记为数字 a1 + 1 到 a1 + a2 等等。请参阅示例以获得更好的理解。

鼹鼠不能吃掉所有的 bug (土拨鼠带来了很多)，而且众所周知，鼹鼠是盲人，所以土拨鼠告诉他最好吃的多汁 bug 的标签。如果鼹鼠正确地说出这条蠕虫包含在哪一堆中，土拨鼠只会给鼹鼠一条蠕虫。

可怜的鼹鼠向你寻求帮助。对于 Marmot 所说的所有多汁蠕虫，请告诉 Mole 正确答案。

输入

第一行包含一个整数n(1≤n≤105)，即堆的数量。

第二行包含n个整数a1,a2,...,an(1≤ai≤103,a1+a2+...+an≤106),其中ai是第i个蠕虫的数量堆。

第三行是一个整数m(1≤m≤105)，土拨鼠说的多汁虫的数量。

第四行m个整数q1,q2,...,qm(1≤qi≤a1+a2+...+an)，多汁虫的标签。

输出

将 m 行打印到标准输出。第i行应包含一个整数，表示标有数字qi的蠕虫所在的堆的编号。

示例输入

输入

5

2 7 3 4 9

3

1 25 11

输出

1

5

3

---

这是我的代码:

#include <iostream>

using namespace std;

int main(){
    int n, m; //as mentioned in Q
    cin >> n;
    int *a = new int[n]; //as said in Q
    for(int i = 0; i < n; i++)
        cin >> a[i];
    cin >> m;
    int *q = new int[m]; //as said in Q
    for(int i = 0; i < m; i++)
        cin >> q[i];
    int *sum = new int[n];
    sum[0] = a[0];
    for(int i = 1; i < n; i++)
        sum[i] = a[i] + sum[i - 1];
    for(int i = 0; i < m; i++){
        int low = 0, high = n - 1, mid;
        while(low <= high){ //here is where I believe has got a problem
            mid = (low + high) / 2;
            if(q[i] >= sum[mid] && q[i] < sum[mid + 1]){
                cout << mid + 1 << endl;
            }
            if(q[i] < sum[mid])
                high = mid - 1;
            else
                low = mid + 1;
        }
    }
    return 0;
}

我不明白问题到底是什么。谁能帮帮我？

提前致谢

编辑:

在我的例子中，这个示例测试的输出是 1。但是，当我尝试在 while block 完成时打印出中间值时，我得到了正确的中间值!

Answer 1

二分查找的问题是您没有处理找不到它要查找的数字的情况。

您的 sum 数组包含 [2, 9, 12, 16, 25]，但是当您查找 1 时，它(完全正确地)找不到它，因为它不在 2 - 25 的范围内。

修复它的一个简单方法是在总和的开头添加一个额外的条目，以便它包含 [0, 2, 9, 12, 16, 25] 那么您的二进制搜索应该找到任何(有效)号码。请记住增加 sum 数组的大小，以及初始 high 值。

解决它的另一种方法是在找到正确的数字时设置一个标志。然后，如果您没有找到该数字，则可以假设它在第一堆中(如果您不需要处理无效输入)。