Cod sursa(job #499955)

Utilizator bogdanvilceleanuBogdan Vilceleanu bogdanvilceleanu Data 11 noiembrie 2010 09:26:33
Problema Cautare binara Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<stdio.h>
long n,v[100005];
long bsdr(long x)
{
	long st=1,dr=n,last=1,med;
	while(st<=dr)
	{
		med=st+((dr-st)>>1);
		if(v[med]<=x)
		{
			last=med;
			st=med+1;
		}
		else
			dr=med-1;
	}
	return last;
}
long bsst(long x)
{
    long st,dr,med,last=1;
    st=1;
    dr=n;
    while(st<=dr)
    {
        med=st+((dr-st)>>1);
        if(x>v[med])
                st=med+1;
        else
        if(x<=v[med])
            {
                dr=med-1;
                last=med;
            }
    }
    return last;
}
int main()
{
	long i,tip,poz,x,m;
	freopen("cautbin.in","r",stdin);
	freopen("cautbin.out","w",stdout);
	scanf("%ld",&n);
	for(i=1;i<=n;i++)
		scanf("%ld",&v[i]);
	scanf("%ld",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%ld",&tip);
		scanf("%ld",&x);
		if(tip==0)
		{
			poz=bsdr(x);
			if(v[poz]==x)
				printf("%ld\n",poz);
			else
				printf("-1\n");
		}
		else
			if(tip==1)
				printf("%ld\n",bsdr(x));
		else
			if(tip==2)
				printf("%ld\n",bsst(x));
	}
	return 0;
}