Ricerca lineare: Python, C++ Esempio

Cos'è l'algoritmo di ricerca?

Un algoritmo di ricerca è progettato per trovare un elemento o un oggetto all'interno di una collezione di elementi o oggetti con una determinata struttura dati. Ad esempio, può essere utilizzato per cercare l'altezza minima in un elenco di altezze, oppure il valore più alto in un elenco o in una matrice di numeri. Alcuni algoritmi di ricerca comuni includono la "Ricerca Lineare", la "Ricerca Binaria", la "Ricerca a Salto", la "Ricerca di Fibonacci", ecc.

Cos'è la ricerca lineare?

Ricerca lineare è uno degli algoritmi di ricerca più semplici. Da una lista o un array dato, cerca l'elemento dato uno per uno. La ricerca lineare itera sull'intera lista e controlla se un elemento particolare è uguale all'elemento cercato. È anche chiamata ricerca sequenziale.

Cosa fa la funzione di ricerca lineare?

Un array di numeri interi è dato come “Numbers,” e una variabile “item” contiene il numero intero da cercare.

Ora, l'algoritmo di ricerca lineare può fornire il seguente output:

• “-1”; questo significa che l’elemento specificato non è stato trovato nell’array.
• Qualsiasi numero compreso tra 0 e n-1; significa che l'elemento di ricerca viene trovato e restituisce l'indice dell'elemento sull'array. Qui, "n" rappresenta la dimensione dell'array.

Come funziona la ricerca lineare?

Supponiamo di avere un array contenente numeri interi. Il compito è trovare un dato numero all'interno dell'array.

• Se il numero si trova nell'array, dobbiamo restituire l'indice di quel numero.
• Se il numero specificato non viene trovato, restituirà -1.

Nel diagramma di flusso, "Dati" è l'array intero, "N" è la dimensione dell'array e "elemento" è il numero che vogliamo cercare nell'array.

Diagramma di flusso per l'algoritmo di ricerca lineare:

Ecco i passaggi del diagramma di flusso:

Passo 1) Leggi l'elemento di ricerca, "elemento".

Passo 2) Inizializza i=0 e index=-1.

Passo 3) Se io

Passo 4) Se Data[i] è uguale a "item", vai al passaggio 5. Altrimenti vai al passaggio 6.

Passo 5) Indice = i (poiché l'elemento si trova all'indice i). Vai al passaggio 8.

Passo 6) io = io+1.

Passo 7) Vai al passaggio 3.

Passo 8) Interrompere.

Per semplicità, forniamo un esempio con un array di numeri interi. La ricerca lineare è applicabile anche nella stringa, in un array di oggetti o in una struttura.

Soprannome Code per l'algoritmo di ricerca sequenziale

Il seguente pseudocodice riproduce la logica della ricerca lineare descritta in precedenza. Il programma scorre l'array a partire dal primo indice e restituisce la posizione in caso di corrispondenza, altrimenti restituisce -1.

function linearSearch: in → Data[], item
    foundAt = -1
    for i in (0 to data.length):
        if data[i] equals item:
            // item is found in the array
            // returning the index
            return i
    // item not found in the array
    // -1 means no item found, as a negative index is not valid
    return -1

C++ Code Esempio di ricerca lineare

Ecco una versione completa C++ Programma che implementa la ricerca sequenziale e stampa l'indice del valore cercato.

#include <bits/stdc++.h>
using namespace std;

int linearSearch(int *arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}

int main() {
    int array[] = {1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10};
    int n = sizeof(array) / sizeof(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

Produzione:

Enter a number to search: -10
-10 is found at index 14

Python Code Esempio di ricerca lineare

La stessa logica in Python utilizza un singolo ciclo sugli indici della lista e restituisce la posizione dell'elemento corrispondente.

def linearSearch(data, item):
    for i in range(len(data)):
        if data[i] == item:
            return i
    return -1

data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else:
    print("{} was not found".format(item))

Produzione:

Enter a number to search: -10
-10 is found at index 14

Analisi della complessità dell'algoritmo di ricerca lineare

In generale, la complessità temporale indica la quantità di tempo CPU necessaria per eseguire una determinata attività. Nell'algoritmo di ricerca lineare, l'attività consiste nel trovare la chiave di ricerca tra gli elementi dell'array.

Esistono tre tipi di complessità temporale:

• Nella peggiore delle ipotesi
• miglior scenario di caso
• Scenario medio

Complessità temporale della ricerca lineare nello scenario peggiore:

Supponiamo di dover eseguire una ricerca lineare in un array di dimensione "n". Possiamo trovare l'elemento cercato tra gli indici da 0 a n-1. Nel caso peggiore, l'algoritmo tenterà di trovare una corrispondenza tra tutti gli elementi dell'array e l'elemento cercato.

In tal caso, la complessità nel caso peggiore sarà O(n). Qui, “O” — notazione O grande — indica la funzione di complessità.

Complessità temporale della ricerca lineare nello scenario del caso migliore:

Supponiamo di cercare un elemento che si trova nella prima posizione dell'array. In questo scenario, l'algoritmo di ricerca lineare non cercherà tutti gli n elementi dell'array. Pertanto, la complessità sarà O(1), ovvero un tempo costante.

Complessità temporale della ricerca lineare nello scenario del caso medio:

Quando un elemento viene trovato all'indice centrale dell'array, si può dire che la complessità media per la ricerca lineare è O(N), dove N indica la lunghezza dell'array.

La complessità spaziale dell'algoritmo di ricerca lineare:

La complessità spaziale per la ricerca lineare è sempre O(N) perché non è necessario memorizzare o utilizzare alcun tipo di variabile temporanea nella funzione di ricerca lineare.

Come migliorare l'algoritmo di ricerca lineare

La ricerca può essere effettuata più volte durante il ciclo di vita del programma. È anche possibile che stiamo eseguendo l'algoritmo di ricerca lineare e cercando una chiave specifica più volte. Possiamo usare il “Algoritmo di ricerca binaria" se l'array è un array ordinato.

Supponiamo che l'array sia composto da 10mila numeri e che l'elemento di destinazione si trovi nel 5000esimo indice. Quindi, l'algoritmo proverà a confrontare 5000 elementi. Ora, i confronti sono attività pesanti per la CPU. Per ottimizzare l'algoritmo di ricerca lineare, abbiamo due opzioni.

• Trasposizione
• Sposta in primo piano

Recepimento:

Con questo metodo, scambieremo l'elemento cercato con il suo elemento precedente nell'array. Ad esempio, supponiamo di avere un array come il seguente:

Dati[] = {1,5,9,8,7,3,4,11}

Ora, vogliamo cercare 4. Fasi di trasposizione:

Passo 1) "4" si trova all'indice 6. Sono stati necessari sei confronti.

Passo 2) Scambia dati[6] e dati[5]. Quindi l'array di dati sarà simile a:

Dati[] = {1,5,9,8,7,4,3,11}

Passo 3) Cerca di nuovo 4. Trovato all'indice 5. Questa volta ci sono voluti cinque confronti.

Passo 4) Scambia data[5] e data[4]. Quindi l'array di dati apparirà così:

Dati[] = {1,5,9,8,4,7,3,11}

Ora, come potete notare, più frequentemente viene cercata una chiave, più diminuisce l'indice. Di conseguenza, diminuisce anche il numero di confronti.

Spostarsi in avanti:

In questo metodo, scambiamo l'elemento da cercare con l'indice 0. Perché se viene cercato di nuovo, possiamo trovarlo in tempo O(1).

Applicazione dell'algoritmo di ricerca lineare

Ecco alcune applicazioni di ricerca lineare che possiamo utilizzare.

• Per array di piccole dimensioni o con pochi elementi nell'elenco, è più semplice utilizzare la ricerca lineare.
• Il metodo di ricerca lineare può essere utilizzato in singolo o array multidimensionali o altre strutture dati.
• In generale, la ricerca lineare è semplice ed efficiente per eseguire una ricerca nei dati “non ordinati”. Possiamo recuperare facilmente un singolo dato dall'elenco non ordinato fornito.

DOMANDE FREQUENTI