Introduzione all'algoritmo di ricerca lineare: introduzione e funzionalità [con esempi]

Che cos'è la ricerca?

La ricerca è il processo per trovare un dato elemento in un elenco di elementi. Aiuta nella ricerca di un record particolare. Pertanto, è una tecnica per identificare il luogo di un determinato oggetto. Il successo di un processo di ricerca dipende dal fatto che l'elemento da cercare sia stato identificato o meno.

La struttura Dati consente la ricerca dei dati attraverso due metodi.

1. Ricerca lineare o ricerca sequenziale
2. Ricerca binaria

Ricerca lineare

Gli algoritmi di ricerca lineare sono un tipo di algoritmo per la ricerca sequenziale dei dati. Questo algoritmo trova un dato elemento con complessità O(n). Viene applicato a una raccolta di oggetti. Ogni singolo elemento dei dati viene ricercato in sequenza e restituito se corrisponde all'elemento cercato. Se non vengono trovate corrispondenze, la ricerca continua fino alla fine dei dati raccolti. È fondamentalmente una tecnica per esplorare ogni elemento mentre si attraversa l'elenco. L'algoritmo di ricerca può essere applicato sia ai dati ordinati che a quelli non ordinati. La ricerca praticamente lineare viene utilizzata raramente a causa delle opzioni di ricerca più veloci fornite da altri algoritmi di ricerca come algoritmi di ricerca binaria e tabelle hash.

Passi nell'algoritmo di ricerca lineare

• Lettura dell'elemento di ricerca da parte dell'utente.
• L'elemento da cercare viene compresso con il primo elemento della lista.
• Se gli elementi corrispondono, viene generato un ritorno.
• Se gli elementi non corrispondono, l'elemento da cercare viene confrontato con il secondo elemento dell'elenco.
• Il processo viene ripetuto finché l'elemento non viene abbinato.

Caratteristiche degli algoritmi di ricerca lineare

1. Di solito viene applicato a un piccolo elenco di dati non ordinati o non ordinati.
2. Il tempo è linearmente dipendente dal numero di elementi, avendo quindi una complessità temporale se O(n).
3. L'implementazione è molto semplice.

Algoritmi di ricerca lineare

Un metodo di ciclo continuo continua a meno che e fino a quando l'elemento non viene trovato

• algoritmo Seqnl_Search(elenco, elemento)
• Pre: elenco != ;
• Posta: restituire l'indice dell'articolo se trovato, altrimenti: 1
• indice <- fi
• while index < list.Cnt and list[index] != item //cnt: variabile contatore
• indice <- indice + 1
• finire mentre
• if index < list.Cnt e list[index] = elemento
• indice di ritorno
• finisci se
• ritorno: 1
• end Seqnl_Search

Esempio di ricerca lineare

Problema: dato un array arr[] di n elementi, scrivere una funzione per cercare un dato elemento x in arr[].

Figura 1: un esempio di codice che mostra l'implementazione dell'algoritmo di ricerca lineare

Fonte

Gli algoritmi di ricerca lineare possono essere utilizzati in diversi linguaggi di programmazione.

1. Ricerca lineare in Python

Figura 2: un esempio di codice che mostra un algoritmo di ricerca lineare in linguaggio Python

Fonte

Output: l'elemento è presente all'indice 3

2. Ricerca lineare in C

Figura 3: un esempio di codice che mostra un algoritmo di ricerca lineare in linguaggio C

Fonte

Output : L'elemento è presente all'indice 3

3. Ricerca lineare nella struttura dei dati

Lo pseudocodice per un problema di ricerca lineare nella struttura dei dati è

Figura 4: Lo pseudocodice per l'algoritmo di ricerca lineare

Fonte

Ricerca binaria

La ricerca binaria è un algoritmo per cercare elementi in una matrice di elementi. Rispetto all'algoritmo di ricerca lineare, l'algoritmo di ricerca binaria viene applicato a un elenco ordinato di dati.

L'algoritmo di ricerca binaria include i seguenti passaggi

• Confronto dell'elemento da cercare con l'elemento al centro dell'elenco o dell'array.
• Se l'elemento corrisponde all'elemento dell'elenco, restituisce l'indice dell'elemento centrale.
• Se non viene restituita alcuna corrispondenza, viene verificato se l'elemento è maggiore o minore dell'elemento al centro.
• Per un elemento di valore maggiore dell'elemento centrale, la ricerca viene effettuata sul lato destro dell'array.
• Allo stesso modo, se l'elemento ha un valore inferiore rispetto all'elemento centrale, la ricerca viene continuata sul lato sinistro dell'elenco.

Pertanto, la ricerca binaria è meglio applicata quando i dati contengono elementi asta di grandi dimensioni in modo ordinato. Ciò rende un requisito per l'algoritmo di ricerca che l'elenco/array debba essere ordinato.

Caratteristiche della ricerca binaria

• L'algoritmo di ricerca binaria è utile per cercare un gran numero di elementi in un array.
• L'algoritmo di ricerca binaria ha una complessità temporale di O(logn).
• L'implementazione di un algoritmo di ricerca binaria è semplice.

Algoritmo di ricerca binaria

• Algoritmo Binary_Search(elenco, elemento)
• Impostare L su 0 e R su n: 1
• se L > R, allora Binary_Search termina senza successo
• altro
• Impostare m (la posizione nell'elemento centrale) sul pavimento di (L + R) / 2
• se Am < T, impostare L su m + 1 e andare al passaggio 3
• se Am > T, impostare R su m: 1 e andare al punto 3
• Ora, Am = T,
• la ricerca è fatta; ritorno (m)

Conclusione

In questo articolo, abbiamo esaminato cos'è un algoritmo di ricerca lineare e abbiamo anche studiato in dettaglio come cercare un determinato elemento da un elenco utilizzando l'algoritmo di ricerca lineare. Infine, abbiamo anche visto come implementare praticamente l'algoritmo di ricerca lineare utilizzando Python 3 come linguaggio e ottenere l'output desiderato.

Se sei interessato alla scienza dei dati, devi dare un'occhiata a IIIT-B e all'Executive PG Program in Data Science di upGrad, che è stato creato con cura per i professionisti che lavorano e offre numerosi casi di studio, workshop pratici, tutoraggio 1 contro 1 e molto di piu.