Cod sursa(job #1249017)
Utilizator | Data | 26 octombrie 2014 13:08:57 | |
---|---|---|---|
Problema | Cautare binara | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.74 kb |
#include<fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");
int n,i,T,m,p,u,tip,x,poz,a[100001];
int main()
{
in>>n;
for(i=1 ; i<=n; i++)in>>a[i];
in>>T;
while(T)
{
in>>tip>>x;
p=1;
u=n;
poz=-1;
if(tip<2)
{
do
{
m=(p+u)/2;
if(a[m]==x)
{
poz=m;
p=m+1;
while(p<=u)
{
m=(p+u)/2;
if(a[m]==x)
{
poz=m;
p=m+1;
}
else u=m-1;
}
}
else if(a[m]<x) p=m+1;
else u=m-1;
}
while(p<=u);
if(tip==1 && poz==-1) poz=u;
out<<poz<<'\n';
}
else
{
do
{
m=(p+u)/2;
if(a[m]==x)
{
poz=m;
u=m-1;
while(p<=u)
{
m=(p+u)/2;
if(a[m]==x)
{
poz=m;
u=m-1;
}
else p=m+1;
}
}
else if(a[m]<x) p=m+1;
else u=m-1;
}
while(p<=u);
if(poz==-1) poz=p;
out<<poz<<'\n';
}
T--;
}
out.close();
return 0;
}