Cod sursa(job #418865)

Utilizator joRicelAvadanei Danut joRicel Data 16 martie 2010 16:41:44
Problema Cautare binara Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <cstdio>
int v[100001],n;
int cb(int a[],int b);
int cb_0(int a[],int b);
int cb_1(int a[],int b);
int cb_2(int a[],int b);
void read();
int main()
{
	int s,c,aux,m;
	read();
	scanf("%d",&m);
	for(int i = 0;i < m;i++)
	{
		scanf("%d %d",&s,&c);
		if(s == 0)
		{
			aux = cb(v,c);
			if(aux != -1)
				printf("%d\n",cb_0(v,aux));
			else printf("-1\n");
		}
		else if(s == 1)
		{
			printf("%d\n",cb_1(v,c));
		}
		else if(s == 2)
		{
			printf("%d\n",cb_2(v,c));
		}
	}
	return 0;
}
void read()
{
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
	{
		scanf("%d",&v[i]);
	}
}
int cb(int a[],int b)
{
	int st,dr,mij;
	st = 0;dr = n;
	while(st <= dr)
	{
		mij = (st + dr) / 2;
		if(b ==  a[mij]) return mij;
		if(b > a[mij])
			st = mij + 1;
		else
			dr = mij - 1;
	}
	return -1;
}
int cb_0(int a[],int b)
{
	while(a[b] == a[b+1] && b <= n)
	{
		b++;
	}
	return b;
}
int cb_1(int a[],int b)
{	
	int st,dr,mij,last = 0;
	st = 0;dr = n;
	while(st <= dr)
	{
		mij = (st + dr) / 2;
		if(b >= a[mij])
			st = mij + 1,last = mij;
		else
			dr = mij - 1;
	}
	return last;
}
int cb_2(int a[],int b)
{
	int st,dr,mij,last = n + 1 ;
	st = 0;dr = n;
	while(st <= dr)
	{
		mij = (st + dr) / 2;
		if(b <= a[mij])
			dr = mij - 1,last = mij;
		else
			st = mij + 1;
	}
	return last;
}