Non passa nemmeno un solo giorno, quando non dobbiamo cercare qualcosa nella nostra vita quotidiana, chiavi della macchina, libri, penna, caricabatterie mobile e cosa no. Stessa è la vita di un computer, ci sono così tanti dati memorizzati in esso, che ogni volta che un utente chiede alcuni dati, computer deve cercare la sua memoria per cercare i dati e renderli disponibili per l’utente. E il computer ha le proprie tecniche per la ricerca attraverso la sua memoria veloce, che si può imparare di più nella nostra serie di tutorial del sistema operativo.
Cosa succede se devi scrivere un programma per cercare un dato numero in un array? Come farai?
Bene, per cercare un elemento in un dato array, ci sono due algoritmi popolari disponibili:
- Ricerca lineare
- Ricerca binaria
Ricerca lineare
La ricerca lineare è un algoritmo di ricerca molto semplice e semplice. Nella ricerca lineare, cerchiamo un elemento o un valore in un dato array attraversando l’array dall’inizio, fino a trovare l’elemento o il valore desiderato.
Confronta l’elemento da cercare con tutti gli elementi presenti nell’array e quando l’elemento viene abbinato correttamente, restituisce l’indice dell’elemento nell’array, altrimenti restituisce -1.
La ricerca lineare viene applicata su elenchi non ordinati o non ordinati, quando ci sono meno elementi in un elenco.
Caratteristiche dell’algoritmo di ricerca lineare
- Viene utilizzato per piccoli elenchi di elementi non ordinati e non ordinati.
- Ha una complessità temporale di O(n), il che significa che il tempo dipende linearmente dal numero di elementi, che non è male, ma non troppo buono.
- Ha un’implementazione molto semplice.
Implementeremo l’algoritmo di ricerca lineare nel prossimo tutorial.
Ricerca binaria
La ricerca binaria viene utilizzata con array o elenco ordinati. Nella ricerca binaria, seguiamo i seguenti passaggi:
- Iniziamo confrontando l’elemento da cercare con l’elemento nel mezzo della lista/array.
- Se otteniamo una corrispondenza, restituiamo l’indice dell’elemento centrale.
- Se non otteniamo una corrispondenza, controlliamo se l’elemento da cercare è minore o maggiore di valore rispetto all’elemento centrale.
- Se l’elemento / numero da cercare ha un valore maggiore del numero centrale, selezioniamo gli elementi sul lato destro dell’elemento centrale(poiché l’elenco / array è ordinato, quindi a destra, avremo tutti i numeri maggiori del numero centrale) e ricominciamo dal passaggio 1.
- Se l’elemento/numero da cercare ha un valore minore rispetto al numero centrale, selezioniamo gli elementi sul lato sinistro dell’elemento centrale e ricominciamo dal passaggio 1.
La ricerca binaria è utile quando ci sono un gran numero di elementi in un array e sono ordinati.
Quindi una condizione necessaria affinché la ricerca binaria funzioni è che l’elenco/array debba essere ordinato.
Caratteristiche di Binary Search
- E ‘ grande per la ricerca attraverso grandi array ordinati.
- Ha una complessità temporale di O(log n) che è una complessità temporale molto buona. Ne discuteremo in dettaglio nel tutorial di ricerca binaria.
- Ha una semplice implementazione.