Cod sursa(job #1122298)

Utilizator RadEmanuelRad Emanuel RadEmanuel Data 25 februarie 2014 17:26:42
Problema Cautare binara Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
using namespace std;
ifstream fin("cautbin.in");
ofstream fout("cautbin.out");
int v[10001],i,n,m,step,poz,x,type;
int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
        fin>>v[i];
    fin>>m;
    for(i=1;i<=m;++i)
    {
        fin>>type>>x;
        step=1;
        while(step<=n) step<<=1;
        for(poz=1;step;step>>=1)
            if(poz+step<=n && v[poz+step]<=x)
                poz+=step;
        if(type==2)
            if(x!=v[poz])
            {
                while(v[poz]<x && poz!=n)
                    ++poz;
                fout<<poz<<'\n';
                continue;
            }
            else
            {
                while(v[poz]==x && poz!=n)
                    --poz;
                fout<<poz+1<<'\n';
                continue;
            }
        if(type==0 && v[poz]!=x)
            fout<<"-1"<<'\n';
        else
            fout<<poz<<'\n';

    }
    return 0;
}