Algoritmo di ricerca binaria con ESEMPIO

Prima di imparare la ricerca binaria, impariamo:

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?

Una 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 fondamentale prevede la divisione dei dati nell'elenco a metà finché il valore richiesto non viene individuato e visualizzato all'utente nel risultato della ricerca. La ricerca binaria è comunemente nota come a ricerca a metà intervallo o 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 ordinato di dati
• Successivamente, il valore della chiave viene confrontato con l'elemento
• Se il valore della chiave è inferiore all'elemento centrale, la ricerca analizza i valori superiori dell'elemento centrale per il confronto e la corrispondenza
• Nel caso in cui il valore della chiave sia maggiore dell'elemento centrale, la ricerca analizza i valori inferiori dell'elemento centrale per il confronto e la corrispondenza

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:

1. Hai una matrice di 10 cifre e l'elemento 59 deve essere trovato.
2. Tutti gli elementi sono contrassegnati con l'indice da 0 a 9. Ora viene calcolata la parte centrale dell'array. Per fare ciò, prendi i valori più a sinistra e a destra dell'indice e li dividi per 2. Il risultato è 4.5, ma prendiamo il valore minimo. Quindi il centro è 4.
3. L'algoritmo elimina tutti gli elementi dal centro (4) al limite inferiore perché 59 è maggiore di 24 e ora l'array rimane con solo 5 elementi.
4. Ora, 59 è maggiore di 45 e minore di 63. Il valore centrale è 7. Quindi il valore dell'indice destro diventa medio – 1, che equivale a 6, e il valore dell'indice sinistro rimane lo stesso di prima, che è 5.
5. A questo punto, sai che 59 viene dopo 45. Quindi, anche l'indice sinistro, che è 5, diventa medio.
6. 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

Diamo un'occhiata al seguente esempio per comprendere il funzionamento della ricerca binaria

1. Hai una serie di valori ordinati che vanno da 2 a 20 e devi individuare 18.
2. La media dei limiti inferiore e superiore è (l + r) / 2 = 4. Il valore cercato è maggiore del valore medio che è 4.
3. I valori dell'array inferiori al valore medio vengono eliminati dalla ricerca e vengono cercati i valori superiori al valore medio 4.
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 da utilizzare come algoritmo di ricerca:

• La ricerca binaria funziona in modo efficiente su dati ordinati, indipendentemente dalla dimensione 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 dei dati ordinati in base a un principio di ordinamento rispetto all'utilizzo di confronti di uguaglianza, che sono più lenti e per lo più imprecisi.
• Dopo ogni ciclo di ricerca, l'algoritmo divide la dimensione dell'array a metà, quindi nell'iterazione successiva funzionerà solo nella restante metà dell'array

Scopri il nostro prossimo tutorial di Ricerca lineare: Python, C++ Esempio

Sintesi

• La ricerca è un'utilità che consente all'utente di cercare documenti, file e altri tipi di dati. Una ricerca binaria è un tipo avanzato di algoritmo di ricerca che trova e recupera dati da un elenco ordinato di elementi.
• La ricerca binaria è comunemente nota come ricerca a mezzo intervallo o ricerca logaritmica
• Funziona dividendo l'array a metà ad ogni iterazione sotto l'elemento richiesto.
• algoritmo binario prende la parte centrale dell'array dividendo la somma dei valori dell'indice più a sinistra e a destra per 2. Ora, l'algoritmo elimina il limite inferiore o superiore degli elementi dal centro dell'array, a seconda dell'elemento da trovare.
• L'algoritmo 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 dei dati ordinati in base a un principio di ordinamento anziché utilizzando confronti di uguaglianza lenti e imprecisi.
• Una ricerca binaria non è adatta per dati non ordinati.