Cod sursa(job #2544550)

Utilizator imihaibBuleu Mihai imihaib Data 12 februarie 2020 11:05:55
Problema Cautare binara Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("cautbin.in");
ofstream fout("cautbin.out");

int v[100000001];
int n, m, a, b, cer, x;

void citire(){
    fin >> n;
    for(int i = 1; i <= n; ++i) fin >> v[i];

    fin >> m;
}

int rez0(){
    int poz = 0;

    for(int p = (1<<30); p > 0; p>>=1){
        if(poz + p <= n && v[poz + p] <= x){
            poz += p;
        }
    }
    if(v[poz] != x) return -1;

    return poz;
}

int rez1(){
    int poz = 0;

    for(int p = (1<<30); p > 0; p>>=1){
        if(poz + p <= n && v[poz + p] <= x){
            poz += p;
        }
    }

    return poz;
}

int rez2(){
    int poz = 0;

    for(int p = (1<<30); p > 0; p>>=1){
        if(poz + p <= n && v[poz + p] < x)
        {
            poz += p;
        }
    }
    poz++;

    return poz;
}

int main()
{
    citire();

    for(int i = 1; i <= m; ++i)
        {
        fin >> cer >> x;
        if(cer == 0)
        {
            fout << rez0() << '\n';
        }
        else if(cer == 1)
        {
            fout << rez1() << '\n';
        }
            else
            {
                fout << rez2() << '\n';
            }
    }
}