Cod sursa(job #766265)
Utilizator | Data | 10 iulie 2012 19:21:16 | |
---|---|---|---|
Problema | Cautare binara | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 3.27 kb |
#include <fstream>
#define dim 100001
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int afla (int[],int,int,int);
int binara (int[],int,int,int);
int main()
{
int v[dim],n,i,caz,x,m,poz;
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i];
fin>>m;
for (i=0;i<m;i++)
{
fin>>caz>>x;
switch (caz)
{
case 0:
poz=binara(v,1,n,x);
if(poz==-1)
fout<<"-1\n";
else
{
poz++;
while (v[poz]==x&&poz<n)
poz++;
fout<<poz-1<<"\n";
}
break;
case 1:
poz=binara(v,1,n,x);
if(poz==-1)
{
poz=afla(v,1,n,x);
if(v[poz]<x)
fout<<poz<<"\n";
else
fout<<poz-1<<"\n";
/*
x--;
poz=binara(v,1,n,x);
while(poz==-1)
{
x--;
poz=binara(v,1,n,x);
}
poz++;
while(v[poz]==x&&poz<n)
poz++;
fout<<poz-1<<"\n";
*/
}
else
{
poz++;
while (v[poz]==x&&poz<n)
poz++;
fout<<poz-1<<"\n";
}
break;
case 2:
poz=binara (v,1,n,x);
if (poz==-1)
{
/*
x++;
poz=binara(v,1,n,x);
while (poz==-1)
{
x++;
poz=binara(v,1,n,x);
}
poz--;
while (v[poz]==x&&poz)
poz--;
fout<<poz+1<<"\n";
*/
poz=afla(v,1,n,x);
if(v[poz]>x)
fout<<poz<<"\n";
else
fout<<poz+1<<"\n";
}
else
{
poz--;
while (v[poz]==x&&poz )
poz--;
fout<<poz+1<<"\n";
}
break;
}
}
//rez=binara (v,0,n-1,5);
// fout<<rez;
return 0;
}
int binara ( int v[dim],int a,int b,int x)
{
int mijl;
mijl=a+(b-a)/2;
if(a<=b)
{
if ( x>v[mijl])
return binara (v,mijl+1,b,x);
else
if (x<v[mijl])
return binara(v,a,mijl-1,x);
else
return mijl;
}
else
return -1;
}
int afla ( int v[dim],int a, int b , int x)
{
int mijl;
mijl=a+(b-a)/2;
if (a!=b)
if( x<v[mijl] )
return afla (v,a,mijl,x);
else
return afla (v,mijl+1,b,x);
else
return a;
}