Cod sursa(job #1321024)
Utilizator | Harhoi Radu RaduH | Data | 18 ianuarie 2015 18:45:56 |
---|---|---|---|
Problema | Cautare binara | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.55 kb |
#include <fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int n,m,a[100010],i,j,x,s,q,ok,poz,k;
int main()
{
fin>>n;
for(i=0;i<n;i++)
fin>>a[i];
fin>>m;
for(i=0;i<m;i++)
{
fin>>q>>x;
switch(q)
{
case 0:
{
for(s=1;s<n;s<<=1);
for(j=0;s;s>>=1)
if(j+s<=n && a[j+s]<=x)
j+=s;
if(j==0 || a[j]!=x)
fout<<"-1\n";
else
fout<<j+1<<'\n';
}break;
case 1:
{
for(s=1;s<n;s<<=1);
for(j=0;s;s>>=1)
{
if(j+s<=n && a[j+s]<x)
j+=s;
}
poz=j;
for(k=poz;k<n;k++)
if(a[k]<=x)
j=k+1;
fout<<j<<'\n';
}break;
case 2:
{
ok=0;
for(s=1;s<n;s<<=1);
for(j=0;s;s>>=1)
if(j+s<=n && a[j+s]<x)
j+=s;
if(j==0 || a[j]!=x)
poz=n-1;
else
poz=j;
for(k=poz;k>=0;k--)
if(a[k]>=x)
j=k+1;
fout<<j<<'\n';
}break;
}
}
fin.close();
fout.close();
return 0;
}