Cod sursa(job #1726293)

Utilizator serbanmaria15Serban Maria-Catalina serbanmaria15 Data 7 iulie 2016 18:12:36
Problema Cautare binara Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include<stdio.h>

int cautBin1(int v[], int inf, int sup, int cautat)
{
	int mijloc;
	while( inf <= sup)
	{
		mijloc = ( inf + sup)/2;
		if( v[mijloc] <= cautat) // daca gasete valoarea marim limita inferioara pentru a vedea daca avem mai avem pe o poz, cu indice mai mare val cautata
			inf = mijloc + 1;
		else
			sup = mijloc - 1;
	}
	mijloc = (inf + sup)/2;
	//daca nu gaseste valoare pe o poz cu indice mai mare, decrementam mijlocul
	if( v[mijloc] > cautat)
		mijloc--;
	if( v[mijloc] == cautat)
		return mijloc;
	return -1;
	
}

int cautBin2(int v[], int inf, int sup, int cautat)
{
	int mijloc;
	while( inf < sup)
	{
		mijloc = ( inf + sup)/2;
		if( v[mijloc] <= cautat) // daca gasete valoarea marim limita inferioara pentru a vedea daca avem mai avem pe o poz, cu indice mai mare val cautata
			inf = mijloc + 1;
		else
			sup = mijloc;
	}
	mijloc = (inf + sup)/2;
	//daca nu gaseste valoare pe o poz cu indice mai mare, decrementam mijlocul
	if( v[mijloc] > cautat)
		--mijloc;
		return mijloc;
}

int cautBin3(int v[], int inf, int sup, int cautat)
{
	int mijloc;
	while( inf < sup)
	{
		mijloc = ( inf + sup)/2;
		if( v[mijloc] < cautat) // daca gasete valoarea marim limita inferioara pentru a vedea daca avem mai avem pe o poz, cu indice mai mare val cautata
			inf = mijloc + 1;
		else
			sup = mijloc;			
	}
	mijloc = (inf + sup)/2;
	//daca nu gaseste valoare pe o poz cu indice mai mare, decrementam mijlocul
	if( v[mijloc] < cautat)
		++mijloc;
		return mijloc;
}


int main()
{
	FILE *inputFile, *outputFile;
	inputFile=fopen("cautbin.in", "r");
	outputFile=fopen("cautbin.out", "w");

	int n,m, tip, v[100000],i, x;
	int cautat1, cautat2, cautat3;
	fscanf(inputFile, "%d", &n);
	for(i=0; i<n; i++)
	{
		fscanf(inputFile, "%d", &v[i]);
	}
	fscanf(inputFile, "%d", &m);
	for(i=0; i<m; i++)
	{
		fscanf(inputFile, "%d", &tip);
		fscanf(inputFile, "%d", &x);
		
		if( tip == 0)
		{
			cautat1 = cautBin1(v, 0, n-1, x);
			fprintf(outputFile, "%d\n", cautat1 +1 );
		}
		if( tip == 1)
		{
			cautat2 = cautBin2(v, 0, n-1, x);
			fprintf(outputFile, "%d\n", cautat2 +1 );
		}
		if( tip == 2)
		{
			cautat3 = cautBin3(v, 0, n-1, x);
			fprintf(outputFile, "%d\n", cautat3 +1);
		}
	}
	return 0;
			

}