Cod sursa(job #1692095)

Utilizator Moise_AndreiMoise Andrei Moise_Andrei Data 20 aprilie 2016 09:21:46
Problema Cautare binara Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("cautbin.in");
ofstream out("cautbin.out");

const int maxn = 100005;

int v[maxn], n, m;

int cautabin1(int x) {
    int st = 1, dr = n;
    int rasp = -1;
    while(st <= dr) {
        int mid = (st + dr) / 2;
        if(v[mid] == x) {
            st = mid + 1;
            rasp = mid;
        }
        else if(v[mid] > x) {
            dr = mid - 1;
        }
        else
            st = mid + 1;
    }
    return rasp;
}
/// 1 x - cea mai mare pozitie pe care se afla un element cu valoarea mai mica sau egala cu x in sir. Se garanteaza ca cel mai mic numar al sirului este mai mic sau egal decat x
int cautabin2(int x) {
    int st = 1, dr = n,rasp=-1;
    while(st <= dr) {
        int mid = (st + dr) / 2;
        if(v[mid] <= x) {
            rasp = mid;
            st = mid + 1;
        }
        else {
            dr = mid - 1;
        }
    }
    return rasp;
}
///2 x - cea mai mica pozitie pe care se afla un element cu valoarea mai mare sau egala cu x in sir. Se garanteaza ca cel mai mare numar din sir este mai mare sau egal decat x

int cautabin3(int x) {
    int st=1,dr=n,rast=-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(v[mid]>=x)
        {
            rast = mid;
            dr = mid-1;
        }
        else{
            st = mid+1;
        }
    }
    return rast;
}

int main()
{
    in >> n;
    for(int i = 1 ; i <= n ; ++ i)
        in >> v[i];
    in >> m;
    for(int i = 1 ; i <= m ; ++ i) {
        int op, x;
        in >> op >> x;
        if(op == 0)
            out << cautabin1(x) << '\n';
        else if(op == 1)
            out << cautabin2(x) << '\n';
        else
            out << cautabin3(x) << '\n';
    }
    return 0;
}