Prima di imparare la ricerca binaria, impariamo:
Cos'è la ricerca?
La ricerca è un'utilità che consente all'utente di trovare documenti, file, supporti o qualsiasi altro tipo di dati contenuti in un database. La ricerca funziona sul semplice principio di abbinare i criteri ai record e di mostrarli 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 i dati da un elenco ordinato di elementi. Il suo principio di funzionamento principale consiste nel dividere a metà i dati nell'elenco fino a quando il valore richiesto non viene individuato e visualizzato all'utente nel risultato della ricerca. La ricerca binaria è comunemente nota come ricerca a mezzo intervallo o ricerca logaritmica .
In questo tutorial sull'algoritmo imparerai:
- Cos'è la ricerca?
- Cos'è la ricerca binaria?
- Come funziona la ricerca binaria?
- Esempio di ricerca binaria
- Perché abbiamo bisogno della ricerca binaria?
Come funziona la ricerca binaria?
La ricerca binaria funziona nel modo seguente:
- Il processo di ricerca inizia individuando l'elemento centrale della matrice di dati ordinata
- 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 nell'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 nell'elemento centrale per il confronto e la corrispondenza
Esempio di ricerca binaria
Vediamo l'esempio di un dizionario. Se hai bisogno di trovare una determinata parola, nessuno passa attraverso ciascuna parola in modo sequenziale, ma individua casualmente le parole più vicine per cercare la parola richiesta.
L'immagine sopra mostra quanto segue:
- Hai un array di 10 cifre e l'elemento 59 deve essere trovato.
- Tutti gli elementi sono contrassegnati con l'indice da 0 a 9. Ora viene calcolata la parte centrale della matrice. Per fare ciò, prendi i valori più a sinistra e più a destra dell'indice e li dividi per 2. Il risultato è 4,5, ma prendiamo il valore minimo. Quindi la metà è 4.
- L'algoritmo rilascia tutti gli elementi dal limite medio (4) al limite più basso perché 59 è maggiore di 24 e ora l'array rimane solo con 5 elementi.
- Ora, 59 è maggiore di 45 e minore di 63. Il valore medio è 7. Quindi il valore dell'indice destro diventa medio - 1, che è uguale a 6, e il valore dell'indice sinistro rimane lo stesso di prima, che è 5.
- A questo punto, sai che 59 viene dopo 45. Quindi, anche l'indice sinistro, che è 5, diventa medio.
- Queste iterazioni continuano fino a quando 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 capire il funzionamento della ricerca binaria
- Hai una matrice di valori ordinati che vanno da 2 a 20 e devi individuare 18.
- La media dei limiti inferiore e superiore è (l + r) / 2 = 4. Il valore cercato è maggiore del valore medio che è 4.
- I valori dell'array inferiori al valore medio vengono eliminati dalla ricerca e vengono cercati i valori maggiori del valore medio 4.
- Questo è un processo di divisione ricorrente fino a quando non viene trovato l'elemento 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 sui dati ordinati, indipendentemente dalla dimensione dei dati
- Invece di eseguire la ricerca passando attraverso 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 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 nella successiva iterazione funzionerà solo nella restante metà dell'array
Sommario
- 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 i 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.
- L'algoritmo binario prende il centro dell'array dividendo la somma dei valori dell'indice più a sinistra e più 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 accurati.
- La ricerca binaria esegue confronti dei dati ordinati in base a un principio di ordinamento piuttosto che utilizzando confronti di uguaglianza lenti e imprecisi.
- Una ricerca binaria non è adatta per dati non ordinati.