Cod sursa(job #196268)

Utilizator marinaMarina Horlescu marina Data 25 iunie 2008 01:57:32
Problema Cautare binara Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
//Cautare binara
#include <stdio.h>
#define INPUT "cautbin.in"
#define OUTPUT "cautbin.out"
#define NMAX 131072

int N, M;

int v[NMAX];

int caut2(int x)
{
	int st = 1, dr = N, mij;
	while(st < dr)
	{
		mij = (st + dr)/2;
		if(v[mij] < x) st = mij+1;
		else dr = mij;
	}
	return st;
}

int caut1(int x)
{
	int st = 1, dr = N, mij;
	while(st < dr)
	{
		mij = (st + dr + 1)/2;
		if(v[mij] > x) dr = mij-1;
		else st = mij;
	}
	return st;
}

int caut0(int x)
{
	int st = 1, dr = N;
	while(st < dr)
	{
		int mij = (st + dr + 1)/2;
		if(v[mij] > x) dr = mij - 1;
		else st = mij;
	}
	
	if(v[st] == x) return st;
	return -1;
}

int main()
{
	freopen(INPUT, "r", stdin);
	freopen(OUTPUT, "w", stdout);
	
	scanf("%d", &N);
	int i;
	for(i = 1; i <= N; ++i) scanf("%d", v+i);
	
	scanf("%d", &M);
	for(i = 1; i <= M; ++i)
	{
		int tip, x;
		scanf("%d %d", &tip, &x);
		
		if(tip == 0) printf("%d\n", caut0(x));
		else if(tip == 1) printf("%d\n", caut1(x));
		else printf("%d\n", caut2(x));
	}
	return 0;
}