Search (Hard Version) Editorial

Explanation
The difference between hard and easy versions is constraints as we can create a count array of size (10^9) it’s better to use Binary Search for Each Query

``````#include<bits/stdc++.h>
using namespace std;
bool bs(int low,int high,int key,int a[])
{
if(low<=high)
{
int mid=(low+high)/2;
if(a[mid]>key)
{
return bs(mid+1,high,key,a);
}
else if(a[mid]<key)
{
return bs(low,mid-1,key,a);
}
else
{
return true;
}
}
return false;
}
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int q;
cin>>q;
while(q--)
{
int x;
cin>>x;
if(bs(0,n-1,x,a))
{
cout<<"1\n";
}
else
{
cout<<"0\n";
}
}
}
``````

Code In C:

``````#include<stdio.h>
int bs(int low,int high,int key,int a[])
{
if(low<=high)
{
int mid=(low+high)/2;
if(a[mid]>key)
{
return bs(mid+1,high,key,a);
}
else if(a[mid]<key)
{
return bs(low,mid-1,key,a);
}
else
{
return 1;
}
}
return 0;
}
int main()
{
int n;
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
int q;
scanf("%d",&q);
while(q--)
{
int x;
scanf("%d",&x);
if(bs(0,n-1,x,a))
{
printf("1\n");
}
else
{
printf("0\n");
}
}
}
``````