Cod sursa(job #2398567)
Utilizator | Data | 5 aprilie 2019 18:58:26 | |
---|---|---|---|
Problema | Cautare binara | Scor | 40 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.81 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int i,N,M,a[100005],logN,lg;
int main()
{
fin >> N;
for(i=1;i<=N;i++)
fin >> a[i];
for(logN=1;logN<=N;logN<<=1);
fin >> M;
for(;M;M--)
{
int t,x;
fin >> t >> x;
if(t<2)
{
for(lg=logN,i=0;lg;lg>>=1)
if(i+lg<=N and a[i+lg]<=x)
i+=lg;
if(t==0 and a[i]!=x)
fout << "-1" << endl;
else
fout << i << endl;
}
else
{
for(lg=logN,i=N;lg;lg>>=1)
if(i-lg>=1 and a[i-lg]>=x)
i-=lg;
fout << i << endl;
}
}
return 0;
}