binary search in a piece of code in c++ seems to have problems

Question

I was participating in an online local contest simulation that I faced a problem while implementing one of the questions. Here is the question:

Description

It is lunch time for Mole. His friend, Marmot, prepared him a nice game for lunch.

Marmot brought Mole n ordered piles of worms such that i-th pile contains ai worms. He labeled all these worms with consecutive integers: worms in first pile are labeled with numbers 1 to a1, worms in second pile are labeled with numbers a1 + 1 to a1 + a2 and so on. See the example for a better understanding.

Mole can't eat all the worms (Marmot brought a lot) and, as we all know, Mole is blind, so Marmot tells him the labels of the best juicy worms. Marmot will only give Mole a worm if Mole says correctly in which pile this worm is contained.

Poor Mole asks for your help. For all juicy worms said by Marmot, tell Mole the correct answers.

Input

The first line contains a single integer n (1 ≤ n ≤ 105), the number of piles.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 103, a1 + a2 + ... + an ≤ 106), where ai is the number of worms in the i-th pile.

The third line contains single integer m (1 ≤ m ≤ 105), the number of juicy worms said by Marmot.

The fourth line contains m integers q1, q2, ..., qm (1 ≤ qi ≤ a1 + a2 + ... + an), the labels of the juicy worms.

Output

Print m lines to the standard output. The i-th line should contain an integer, representing the number of the pile where the worm labeled with the number qi is.

Sample Input

Input

5

2 7 3 4 9

3

1 25 11

Output

1

5

3

---

And here is my code:

#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;
}

I cannot understand what the problem really is. Can anybody help me out?

Thanks in advance

Edit:

The output for this sample test is 1 in my case. However, when I attempt to print out mid when while block is done, I get the correct mid values!

• Benjamin Bannier: It would be helpful if you could share the problem you were having.
• Gilson PJ: may be he is talking about this contest codeforces.com/problemset/problem/474/B
• Gilson PJ: This is a contest and you are participating, I believe this is not the correct way to find out the solution. Try your self.
• John3136: Variables names n, m. i, q, h, l. Not a comment to be seen. You could help others (and yourself) by using decent variable names!
• Athena: I am not participating right now. It is done. I am just trying to solve my own problem. I could not send it due to the problem and now I am trying to fix it So to learn something new.

Answer 1

The problem with your binary search is that you don't handle the case where it fails to find the number it is looking for.

Your sum arrays holds [2, 9, 12, 16, 25], but when you look for 1, it (quite rightly) doesn't find it as it is not in the range of 2 - 25.

One easy way to fix it is to add an extra entry at the start of your sum so that it contains [0, 2, 9, 12, 16, 25] then your binary search should find any (valid) number. Remember to increase the size of your sum array, as well as the initial high value.

The other way to fix it would be to set a flag when you find the right number. Then, if you don't find the number, you can assume it is in the first pile (if you don't need to handle invalid input).

Answer 2

First, make it work. Then make it fast.

Replace the binary search with a simple linear scan, and you'll quickly see that the conditions you wrote down are incorrect. Worm 1 is in the first pile for instance. Given the problem conditions I expect linear scanning is fast enough to work.

• Athena: linear search just worked fine but it did not meet the limitations. but thanks any way