Cod sursa(job #2588756)

Utilizator KernelovicNegrean Victor Kernelovic Data 25 martie 2020 13:36:09
Problema Cautare binara Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <bits/stdc++.h>

using namespace std;

int sir[100005], n;

int pozMin(int x)
{
	int left = -1, right = n - 1, mid;
	
	while(right - left > 1)
	{
		mid = left + (right - left) / 2;
		if(sir[mid] >= x) right = mid;
		else left = mid;
	}
	
	return right;
}

int pozMax(int x)
{
	int left = 0, right = n, mid;
	
	while(right - left > 1)
	{
		mid = left + (right - left) / 2;
		if(sir[mid] > x) right = mid;
		else left = mid;
	}	
	
	return left;
}

int main()
{
	ifstream in("cautbin.in");
	ofstream out("cautbin.out");
	
	in >> n;
	
	for(int i = 0; i < n; i++)
	{
		in >> sir[i];
	}
	
	int op, cerinta, nr; 
	in >> op;
	
	for(int i = 0; i < op; i++)
	{
		in >> cerinta >> nr;
		switch(cerinta) {
			case 0:{int lower_b = pozMax(nr);
				    if(sir[lower_b] != nr) out << -1 << '\n';
			        else out << ++lower_b << '\n';
			        break;}
			case 1: out << pozMax(nr) + 1 << '\n'; break;
			case 2: out << pozMin(nr) + 1 << '\n';
		}
	}
}