Algoritmo di ricerca binaria con ESEMPIO
Team editoriale
⚡ Riepilogo intelligente
L'algoritmo di ricerca binaria trova un elemento in un elenco ordinato dimezzando ripetutamente l'intervallo di ricerca e confrontando l'elemento cercato con quello centrale. Chiamato anche ricerca a intervalli dimezzati o logaritmica, è molto più veloce rispetto alla scansione di ogni singolo elemento.
Prima di imparare la ricerca binaria, impariamo cos'è la ricerca.
Cos'è la ricerca?
La ricerca è un'utilità che consente all'utente di trovare documenti, file, contenuti multimediali o qualsiasi altro tipo di dati contenuti in un database. La ricerca funziona secondo il semplice principio di abbinare i criteri ai record e di visualizzarli all'utente. In questo modo funziona la funzione di ricerca più elementare.
Cos'è la ricerca binaria?
La ricerca binaria è un tipo avanzato di algoritmo di ricerca che trova e recupera dati da un elenco ordinato di elementi. Il suo principio di funzionamento principale consiste nel dividere i dati nell'elenco a metà finché non viene individuato il valore richiesto e visualizzato all'utente nel risultato della ricerca. La ricerca binaria è comunemente nota come ricerca a metà intervallo ricerca logaritmica.
Come funziona la ricerca binaria?
La ricerca binaria funziona nel modo seguente:
- Il processo di ricerca inizia individuando l'elemento centrale dell'array di dati ordinato.
- Dopodiché, il valore della chiave viene confrontato con l'elemento.
- Se il valore della chiave è inferiore all'elemento centrale, la ricerca analizza i valori superiori all'elemento centrale per confrontarli e trovare una corrispondenza.
- Nel caso in cui il valore della chiave sia maggiore dell'elemento centrale, la ricerca analizza i valori inferiori all'elemento centrale per confrontarli e trovare una corrispondenza.
Algoritmo di ricerca binaria (pseudocodice)
La ricerca binaria può essere scritta come una breve routine iterativa. Mantiene due puntatori, basso e alto, e restringe l'intervallo finché non viene trovato l'obiettivo o l'intervallo non è vuoto.
binarySearch(array, target)
low = 0
high = length(array) - 1
while low <= high
mid = (low + high) / 2 // floor value
if array[mid] == target
return mid
else if array[mid] < target
low = mid + 1
else
high = mid - 1
return -1 // target not found
La routine restituisce l'indice del target in caso di successo e -1 quando il valore non è presente. Poiché l'intervallo si dimezza ad ogni passaggio, il ciclo viene eseguito al massimo log₂(n) volte.
Esempio di ricerca binaria
Prendiamo l'esempio di un dizionario. Se devi trovare una certa parola, nessuno esamina ogni parola in modo sequenziale, ma individua casualmente le parole più vicine per cercare la parola richiesta.
L'immagine sopra illustra quanto segue:
- Hai una matrice di 10 cifre e l'elemento 59 deve essere trovato.
- Tutti gli elementi sono contrassegnati da un indice da 0 a 9. Ora, si calcola il valore centrale dell'array. Per farlo, si prendono i valori più a sinistra e più a destra dell'indice e li si divide per 2. Il risultato è 4.5, ma si prende la parte intera inferiore. Quindi il valore centrale è 4.
- L'algoritmo elimina tutti gli elementi dal centro (4) al limite inferiore, perché 59 è maggiore di 24, e ora l'array è composto da soli 5 elementi.
- Ora, 59 è maggiore di 45 e minore di 63. Il valore centrale è 7. Quindi il valore dell'indice di destra diventa il valore centrale - 1, che è uguale a 6, e il valore dell'indice di sinistra rimane lo stesso di prima, cioè 5.
- A questo punto, sai che 59 viene dopo 45. Quindi, anche l'indice sinistro, che è 5, diventa medio.
- Queste iterazioni continuano finché l'array non viene ridotto a un solo elemento o l'elemento da trovare diventa il centro dell'array.
esempio 2
Analizziamo il seguente esempio per comprendere il funzionamento della ricerca binaria.
- Hai una serie di valori ordinati che vanno da 2 a 20 e devi individuare 18.
- La media tra il limite inferiore e quello superiore è (l + r) / 2 = 4. Il valore cercato è maggiore del valore medio, che è 4.
- I valori dell'array inferiori al valore medio vengono esclusi dalla ricerca, mentre vengono cercati i valori superiori al valore medio pari a 4.
- Questo è un processo di divisione ricorrente finché non viene trovato l'oggetto effettivo da cercare.
Perché abbiamo bisogno della ricerca binaria?
I seguenti motivi rendono la ricerca binaria una scelta migliore come algoritmo di ricerca:
- La ricerca binaria funziona in modo efficiente su dati ordinati, indipendentemente dalle dimensioni dei dati.
- Invece di eseguire la ricerca esaminando i dati in sequenza, l'algoritmo binario accede in modo casuale ai dati per trovare l'elemento richiesto. Ciò rende i cicli di ricerca più brevi e più accurati.
- La ricerca binaria esegue confronti tra dati ordinati basandosi su un principio di ordinamento anziché utilizzare confronti di uguaglianza, che sono più lenti e per lo più imprecisi.
- Dopo ogni ciclo di ricerca, l'algoritmo divide a metà la dimensione dell'array; pertanto, nell'iterazione successiva, lavorerà solo sulla metà rimanente dell'array.
Scopri il nostro prossimo tutorial su Ricerca lineare: Python, C++ Esempio.
Ricerca binaria vs ricerca lineare
La ricerca binaria e la ricerca lineare sono i due metodi più comuni per trovare un valore in una collezione. La tabella seguente evidenzia le differenze tra i due:
| Aspetto | Ricerca binaria | Ricerca lineare |
|---|---|---|
| Requisito dei dati | Richiede dati ordinati | Funziona con dati ordinati o non ordinati |
| Metodo | Dimezza il raggio di ricerca a ogni passaggio | Verifica ogni elemento in sequenza |
| Complessità temporale | O (log n) | O (n) |
| migliori per | Grandi insiemi di dati ordinati | Insiemi di dati piccoli o non ordinati |
In sintesi, la ricerca binaria è molto più veloce su grandi quantità di dati ordinati, mentre la ricerca lineare è più semplice ed è l'unica opzione quando i dati non sono ordinati.
