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}; // Dichiarazione e inizializzazione dell'array ordinato
int i = 0, j = N - 1, m, pos = -1; // Inizializzazione degli indici e variabile per la posizione del numero trovato
// Ciclo di ricerca binaria
do {
m = (i + j) / 2; // Calcolo dell'indice medio
if (a[m] == x) { // Se il numero è stato trovato
pos = m; // Memorizza la posizione del numero
} else if (a[m] < x) { // Se il numero nella posizione media è minore di x, cerca nella metà superiore
i = m + 1;
} else { // Se il numero nella posizione media è maggiore di x, cerca nella metà inferiore
j = m - 1;
}
} while (i <= j && pos == -1); // Continua finché gli indici non si sovrappongono o il numero è stato trovato
// Stampa il risultato
if (pos != -1) {
cout << "Numero trovato in posizione: " << pos << endl;
} else {
cout << "Numero non trovato" << endl;
}
return 0;
}
Il caso peggiore si ha quando la chiave non viene trovata nell’array e in questo caso l’iterazione viene eseguita log2 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++
Esercitazione sugli array in C++
Passaggio di parametri per valore o per riferimento
Equazioni di secondo grado in C++
Le variabili globali e loali in C++
Definizione di funzioni in C++
Esercizi con switch case in C++
Successione di Fibonacci in C++
Programmatore professionista.
Cara Cristina,
volevo correggere due errore logici presenti nel programma:
1) dopo la condizione if(a[m]==x), pos=i andrebbe sostituito con pos=m;
2) nella condizione if(a[i]<x), l'indice i andrebbe sostituito con m;
Spero di vedere un cambiamento nel programma in quanto potrebbe far sbagliare molti utenti.
Grazie, gentilissimo. Appena corretto!