L’algoritmo di ricerca binaria o dicotomica è un algoritmo che viene utilizzato per trovare elementi in un array ordinato. Si usa il termine dicotomica (dal greco: tagliare in due) perché si procede a divisioni successive dell’array.

Questo algoritmo rientra dunque nella famiglia degli algoritmi che utilizzano il metodo divide et impera.

Utilizzare la ricerca binaria in un array ordinato è molto più efficiente rispetto alla ricerca sequenziale, in special modo se l’array contiene tanti elementi.

Questo algoritmo viene utilizzato in molte applicazioni in maniera naturale, come ad esempio il gioco indovina numero, la ricerca di una parola in un vocabolario o la ricerca di un contatto telefonico in una rubrica. Quindi ad esempio in quest’ultimo caso, si apre la rubrica, verso l’elemento centrale (poi vedremo come migliorare la ricerca con un algoritmo di ricerca interpolato), quindi si confronta il valore trovato con la chiave da cercare.

Se la chiave è uguale abbiamo trovato subito l’elemento.

Altrimenti, se la chiave è maggiore allora si confronta con i valori successivi, scartando quelli precedenti, cioè gli elementi a destra del valore centrale.

Infine se la chiave è minore si confronta con i valori precedenti, scartando i successivi, cioè gli elementi a sinistra del valore centrale.

Questo chiaramente per un array ordinato in ordine crescente.

Algoritmo di ricerca binaria in C++

Quindi iniziamo confrontando l’elemento x da ricercare con l’elemento intermedio dell’array. L’indice m di questo elemento viene calcolato sommando l’indice inferiore i dell’array in posizione 0 con quello superiore j in posizione N-1 e dividendolo per due: m=(i+j)/2.

Quindi si possono presentare i casi descritti sopra per cui se l’elemento coincide con x allora setto la variabile pos a 1 in modo da uscire dal do while. Altrimenti continuo a cercare tra i valori maggiori o minori a seconda che la chiave x sia maggiore o minore. In ogni caso continuo a cercare finché i non sarà minore o uguale a j.

Ecco quindi il listato completo dell’algoritmo per la ricerca binaria in C++.

#include <iostream>
using namespace std;

#define x 15
#define N 5

int main(){
    int a[N] = {1,5,8,10,15};
    int i = 0, j = N-1, m, pos = -1;
    
    do { 
	m = (i + j)/2;
	if(a[m] == x)  
		pos = m;
	else if (a[m] < x)
		i = m + 1;
	else
		j = m - 1;
    } while(i <= j && pos == -1);	

    if(pos != -1)
	cout<<"numero trovato in posizione: "<<pos<<endl;
    else 
	cout<<"numero non trovato";
	
	return 0;
}

Il caso peggiore si ha quando la chiave non viene trovata nell’array e in questo caso l’iterazione viene eseguita log₂ N volte.

La ricerca binaria ha quindi complessità asintotica O(log N). Spesso infatti questo algoritmo viene definito di ricerca logaritmica.

Ricordiamo che la ricerca sequenziale invece passa da O(n) come caso peggiore a O(n/2) nel caso medio, fino a O(1) se l’elemento si trova in prima posizione.

Prossimamente vedremo l’algoritmo per la ricerca binaria sviluppato in maniera ricorsiva.

Alcuni link utili

Indice argomenti linguaggio C++

Esercizi con gli array in C++

Esercitazione sugli array in C++

Array in C++

Passaggio di parametri per valore o per riferimento

Equazioni di secondo grado in C++

Le variabili globali e loali in C++

Uso delle funzioni in C++

Funzioni in C++

Definizione di funzioni in C++

Libreria cmath

Come usare il for in C++

Massimo tra n numeri in C++

Iterazioni in C++

Ciclo while in C++

Ciclo do while

Operatori logici in C++

Esercizi con switch case in C++

If else in C++

Casting in C++

Tutorial C++

Successione di Fibonacci in C++