Search (Hard Version) Editorial

1

Problem Link

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");
        }
    }
}