Mai intai trebuie sa te autentifici.
Cod sursa(job #445708)
Utilizator | Data | 24 aprilie 2010 12:14:45 | |
---|---|---|---|
Problema | Cautare binara | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.96 kb |
#include<fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int main(){
int n,i,v[100001],x,m,dr,st,cod,gasit,q,j;
in>>n;
for(i=1;i<=n;i++)
in>>v[i];
in>>q;
for(j=1;j<=q;j++)
{
in>>cod>>x;
st=1;
dr=n;
gasit=0;
while(st<dr && gasit==0)
{
m=(st+dr)/2;
if(x==v[m])
gasit=1;
else
if(x>v[m])
st=m+1;
else
dr=m-1;
}
if(cod==0)
{
if(gasit==1)
{
i=m;
while(v[i+1]==x)
i++;
out<<i<<"\n";
}
else
out<<"-1\n";
}
else
if(cod==1)
{
if(gasit==1)
{
i=m;
while(v[i+1]==x)
i++;
out<<i<<"\n";
}
else
{
if(v[m]>x)
m--;
out<<m<<"\n";
}
}
else
{
if(gasit==1)
{
i=m;
while(v[i-1]==x)
i--;
out<<i<<"\n";
}
else
{
if(v[m]<x)
m++;
out<<m<<"\n";
}
}
}
return 0;
}