Feedback for WAV2 problem

feedback
,
1

Learning course: Binary Search
Problem Link: CodeChef: Practical coding for everyone

Feedback

Here’s my code:
include
include
include
using namespace std;

long long binarySearch(vector roots, int N, int key){
int start = 0;
int end = N-1;
int mid = 0;
int pivot = 0;
while(start<=end){
mid = start + (end-start)/2;
if(key<roots[mid]){
end = mid-1;
pivot = mid;
}
else if(key>roots[mid]){
start = mid+1;
pivot = mid+1;
}
else{
return -1;
}
}
return pivot;
}

int main() {
int N, Q;
cin >> N >> Q;
vector roots;
for (int i = 0; i < N; i++) {
long long input;
cin >> input;
roots.push_back(input);
}

sort(roots.begin(), roots.end());

for (int i = 0; i < Q; i++) {
    int key;
    cin >> key;
    int index;
    index = binarySearch(roots, N, key);
    if (index == -1) {
        cout << "0" << endl;
    } 
    else if ((N - index) % 2 == 0) {
        cout << "POSITIVE" << endl;
    }
    else {
        cout << "NEGATIVE" << endl;
    }
}

return 0;

}

I am unable to find the reason for Time Limit Exceeded problem. Changing the sorting algorithm doesn’t work, I’ve tried implementing quick sort, merge sort but still I get TLE. I have seen other people’s approach and it’s almost the same as mine.

2

@lone_coder1
plzz refer the following solution for better understanding of the logic and implementation.

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int n,q;
	cin>>n>>q;
	int a[n];
	for(int i=0;i<n;i++)
	{
	    cin>>a[i];
	}
	sort(a,a+n);
	while(q--)
	{
	    int t;
	    cin>>t;
	    int l=lower_bound(a,a+n,t)-a;
	    if(l==n)
	    cout<<"POSITIVE";
	    else if(a[l]==t)
	    cout<<"0";
	    else 
	    {
	        int d=n-l;
	        if(d%2)
	        cout<<"NEGATIVE";
	        else
	        cout<<"POSITIVE";
	    }
	    cout<<endl;
	}
	return 0;
}