• Autore: Antonio Guadagno
• Fonte: Seneta.it

Ricerca dicotomica o binaria all’interno di un array

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
	int Vettore[]= {-15, -1, 0, 2, 4, 5, 6, 12, 14, 20, 22, 25};
	short Dimensione = sizeof(Vettore)/sizeof(Vettore[0]);
	short PrimoIndice=0, UltimoIndice=Dimensione-1, IndiceMedio;
	int Numero;

	cout << "Elementi dell'array: " << Dimensione << endl;	
	cout << "Primo Elemento: " << Vettore[0] << endl;
	cout << "Ultimo Elemento: " << Vettore[Dimensione-1] << endl;

	// gestione dell'input	
	do{
		cout << endl << "Inserire il numero da cercare: ";
		cin >> Numero;
		if(Numero<Vettore[0] || Numero>Vettore[Dimensione-1])
			cout << endl << "Valore esterno all'array" << endl;
	}while (Numero<Vettore[0] || Numero>Vettore[Dimensione-1]);
	
	// inizio procedura di ricerca dicotomica	
	while(PrimoIndice<=UltimoIndice)
	{
		IndiceMedio=(UltimoIndice+PrimoIndice)/2;
		if (Vettore[IndiceMedio]==Numero)
		{
			cout << endl << "Il Valore risulta presente alla posizione: " 
			<< IndiceMedio;
			return 0;
		}
		if (Vettore[IndiceMedio]<Numero)
			PrimoIndice=IndiceMedio+1; // viene scartata la metà di sinistra
		else
			UltimoIndice=IndiceMedio-1; // viene scartata la metà di destra
	}
	// A questo punto il valore immesso non risulta presente nell'array
	cout << endl << "Il Valore non risulta presente nell'array."; 
}

Visite: 1662

Dispense Scolastiche, Dispense Scolastiche: Informatica

array, Coding, Informatica, Linguaggi di Programmazione