# Cod sursa(job #2433120)

Utilizator Data 25 iunie 2019 21:13:40 Cautare binara 100 cpp-64 done Arhiva educationala 1.55 kb
``````#include <fstream>
#include <assert.h>

int binary_search(int n, int v[], int x) {
int left = 1, middle, right = n;

while (left <= right) {
middle = left + (right - left) / 2;

if (v[middle] <= x) {
left = middle + 1;
} else {
right = middle - 1;
}
}

middle = (left + right) / 2;

if (v[middle] > x) {
--middle;
}

if (v[middle] == x) {
return middle;
}

return -1;
}

int lower_bound(int n, int v[], int x) {
int left = 1, middle, right = n;

while (left < right) {
int middle = left + (right - left) / 2;

if (v[middle] < x) {
left = middle + 1;
} else {
right = middle;
}
}

middle = left + (right - left) / 2;

if (v[middle] < x) {
++middle;
}

return middle;
}

int upper_bound(int n, int v[], int x) {
int left = 1, middle, right = n;

while (left < right) {
middle = left + (right - left) / 2;

if (v[middle] < x) {
left = middle + 1;
} else {
right = middle;
}
}

middle = left + (right - left) / 2;

if (v[middle] > x) {
--middle;
}

return middle;
}

int main() {
std::ifstream cin("cautbin.in");
std::ofstream cout("cautbin.out");
std::ios::sync_with_stdio(false);
int n, m, x, t;

cin >> n;
assert(1 <= n && n <= 100000);
int v[n];

for (int i = 1 ; i <= n ; ++i) {
cin >> v[i];
}

cin >> m;
assert(1 <= m && m <= 100000);

for (; m ; --m) {
cin >> t >> x;
switch(t) {
case 0:	cout << binary_search(n, v, x) << '\n'; break;
case 1: cout << upper_bound(n, v, x) << '\n'; break;
case 2:	cout << lower_bound(n, v, x) << '\n'; break;
default: break;
}
}

return 0;
}``````