// this algorithm is helping to insert a new value in a sorted array and array remaining same;
#include<bits/stdc++.h>
using namespace std;
long long int start,mid,en,in;
vector <long long int>A;
long long int search_lowerbound(long long int key,long long int length)
{
start=0;
en=length-1;
in=-1;
while(start<=en)
{
mid=(start+en)/2;
if(A[mid]==key)
{ in=mid;
en=mid-1;
}
else if(key>A[mid])
{
start=mid+1;
}
else if(key<A[mid])
{
en=mid-1;
}
}
return start;
}
//using boundary algorithm to find a index such a way that its previous and next value is not equal to that value given .
int main()
{
long long int n,m,x,low,high,ind,i;
cin>>n;
for(i=0;i<n;i++)
{
cin>>x;
A.push_back(x);
}
A.erase(unique(A.begin(), A.end()),A.end());
cin>>m;
for(i=1;i<=m;i++)
{
cin>>x;
in=search_lowerbound(x,n);
//cout<<in<<endl<<endl;
if(A[in]==x)
{
low=in-1;
high=in+1;
}
else if(A[in]>x)
{
low=in-1;
high=in;
}
else
{low=in;
high=in+1;
}
if(low!=n&&high!=n)
{
if(low>=0)
cout<<A[low]<<" "<<A[high]<<endl;
else
cout<<"X "<<A[high]<<endl;
}else if(low>=n)
{
if(A[low-1]>x)
cout<<"X X"<<endl;
else
cout<<A[low-1]<<" X"<<endl;
}
else if(high>=n)
cout<<A[low]<<" X"<<endl;
}
return 0;
}
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.