Binary Search Problem C++

the problem:
Senorita likes stones very much. As she is fond of collecting beautiful stones, everyday she finds some of the stones beautiful and collects it in her bottle.

You are given the number of stones, she collects each day for N numbers of days, starting from the very first day. Now you are given Q queries, in each query her friend shambhavi asks you the number of days she has taken to collect M number of stones. Please note that each query contains the different number of M.

Input:
First line contains N and Q , the number of days and number of queries. Second line contains N integers, in which ith integer denotes the number of stones she has collected on ith day.
Then next line contains Q space-separated integers, M , where ith M denotes the ith query, i.e., number of stones.

Output:
For each of the Q queries, you have to output the number of days she has taken to collect M number of stones in a new line.

Constraints:

1 <= N, Q <= 5*10^5
1 <= A[i] <= 10^5
1 <= M <= sum of all the elements in the array.

SAMPLE INPUT
5 4
1 2 3 4 5
3 8 10 14
SAMPLE OUTPUT
2
4
4
5

the function bin() which takes input as the whole array,size of the array and the number x which is user input:
int bin(int arr[],int n,int x){
int l=0,r =n-1;
int ans=-1;
while (l <= r) {
int m = (r+l)/2;
if(arr[m]>=x){
if(arr[m] == x){
ans = m+1;
break;
}
else if(arr[m]>x && arr[m-1]<x){
ans = m+1;
break;
}
else if(arr[m]>x && arr[m-1]==x){
ans = m;
break;
}
else if(arr[m]>x && arr[m-1]>x)
r= m-1;
}
else
l = m+1;
}
if(ans == -1)
return n;
else return ans;
}

i am only able to pass the sample testcases which i showed above and 1 small test case . Please tell me what is wrong in my code.

int bin(int arr[], int n, int x)
{
    int l = 0, r = n - 1;
    while (l < r)
    {
        int m = (r + l) / 2;

        if (arr[m] >= x)
        {
            r = m;
        }
        else
        {
            l = m + 1;
        }
    }

    return (l+1);
}

Try replacing your bin function with the above code.
Pass the prefix_sum array, its size and the value to be searched respectively.

You do not have to break anywhere.
If you just let binary search complete its normal course and handle your pointers correctly, the required answer will be present in the low pointer when the while condition terminates.

In this case,
If we find a position which has a value >= x, we move towards the left part of the array to find a position smaller than the current mid which might contain the answer
Else, we move right to find a position that satisfies the above required condition.

Edit: As your answer is 1 based indexing, I return l+1 instead of l.

I suggest you trace the above code with an example for a better understanding.

I hope this helps! :slightly_smiling_face:

1 Like

https://ideone.com/c4YIj0

  1. use long long int instead of int.
  2. use 1 based index to avoid underflow at m-1 when m may be 0.
  3. turn off sync with stdio to finally pass second testcase.

i Have 1 more problem related to binary search only…
link:
Gaurav And Sub-array | Practice Problems

my code:
UP65XF - Online C++ Compiler & Debugging Tool - Ideone.com
I am not able to pass some of the test case.

Seems like all you have to do is initialize the value of r before starting binary search as β€œn” instead of β€œ100000” :stuck_out_tongue:

1 Like

Ohh my bad :smiley: got it :slight_smile: