Cod sursa(job #516848)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 26 decembrie 2010 18:26:28
Problema Cautare binara Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include<stdio.h>
#define N 100001
long binar2(long v[N],long n,long y)
{long i,step;
for(step=1;step<n;step<<=1);
for(i=0;step;step>>=1)
if(i+step<n&&v[i+step]<=y)
        i+=step;
return i;}

long binar1(long v[N],long n,long y)
{long i,step;
for(step=1;step<n;step<<=1);
for(i=n;step;step>>=1)
if(i-step>1&&v[i-step]>=y)
        i-=step;
return i;}

long binar0(long v[N],long n,long y)
{long i,step;
for(step=1;step<n;step<<=1);
for(i=0;step;step>>=1)
if(i+step<n&&v[i+step]<=y)
        i+=step;
if(v[i]==y)
      return i;
return -1;}

int main()
{long n,m,i,x,y,v[N];
freopen("cautbin.in","r",stdin);
freopen("cautbin.out","w",stdout);
scanf("%ld",&n);
for(i=1;i<=n;i++)
       scanf("%ld",&v[i]);
scanf("%ld",&m);
for(i=1;i<=m;i++)
       {scanf("%ld%ld",&x,&y);
       if(x==0)
              printf("%ld\n",binar0(v,n,y));
       else
              if(x==1)
                       printf("%ld\n",binar1(v,n,y));
              else
                       printf("%ld\n",binar2(v,n,y));}
fclose(stdin);
fclose(stdout);
return 0;}