Cod sursa(job #196580)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 27 iunie 2008 12:29:41
Problema Cautare binara Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <stdio.h>
#define Nmax 100001

int n,m,x,y,r,i;
int v[Nmax];



void cautarebinara0(int a,int b,int c)
{
while(a<=b)
    {
	c=(a+b)/2;
	if (v[c]==x)
	{
	    printf("%d\n",c);
	    return ;
	}
	if(v[c]<x) a=c+1;
	else b=c-1;
    }
    if(v[c]==x)
    {
	printf("%d\n",c);
	return;
    }
    printf("-1\n");
}


void cautarebinara1(int a,int b,int c)
{
    while(a<b)
    {
	c=(a+b)/2;
	if (v[c]<x)
	    a=c+1;
	else
	    b=c;
    }
    c=(a+b)/2;
    if (v[c]>x)
	--c;
    printf("%d\n", c);
}


void cautarebinara2(int a,int b,int c)
{
    while(a<b)
    {
	c=(a+b)/2;
	if (v[c]<x)
	    a=c+1;
	else
	    b=c;
    }
    c=(a+b)/2;
    if (v[c]<x)
	++c;
    printf("%d\n", c);
}


int main(){
freopen("cautbin.in", "r",stdin);
freopen("cautbin.out", "w",stdout);
scanf("%d", &n);
for(i=1;i<=n;++i)
scanf("%d",&v[i]);
scanf("%d", &m);
for(i=1;i<=m;++i)
    {
	scanf("%d%d", &y,&x);
	switch(y)
	{
	    case 0: {cautarebinara0(1,n,x); break;}
	    case 1: {cautarebinara1(1,n,x); break;}
	    case 2: {cautarebinara2(1,n,x); break;}
	}
    }
return 0;
}