Ricerca lineare: Python, C++ Esempio

Cos'è l'algoritmo di ricerca?

Un algoritmo di ricerca è progettato per trovare un elemento o un oggetto da una raccolta di elementi o oggetti con una data struttura dati. Ad esempio, cercare l'altezza minima da un dato elenco di altezze, o cercare il punteggio più alto da un elenco o array di numeri. Pochi algoritmi di ricerca popolari includono "Ricerca lineare", "Ricerca binaria", "Ricerca a salti", "Ricerca di Fibonacci", ecc.

Cos'è la ricerca lineare?

La ricerca lineare è uno degli algoritmi di ricerca più semplici. Da un dato elenco o array, cerca l'elemento dato uno per uno. La ricerca lineare scorre l'intero elenco e controlla se qualche elemento particolare è uguale all'elemento di ricerca. È anche chiamato il 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”; ciò 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?

Diciamo un array contenente numeri interi. Il compito è trovare un determinato numero nell'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) Inizia i=0 e indice=-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 nell'indice n. 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.

Pseudo codice per algoritmo di ricerca sequenziale

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 negative index is not valid
return -1

C++ Esempio di codice Ricerca lineare

#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(arr[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(arr, 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 Esempio di codice Ricerca lineare

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 genere, la complessità temporale indica la quantità di tempo della CPU per eseguire un determinato compito. Nell'algoritmo di ricerca lineare, il compito è trovare la chiave di ricerca dall'elemento 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:

Diciamo che dobbiamo eseguire una ricerca lineare in un array con una dimensione “n”. Possiamo trovare l'elemento di ricerca tra l'indice 0 e n-1. Nel peggiore dei casi, l'algoritmo proverà a far corrispondere tutti gli elementi dell'array con l'elemento di ricerca.

In tal caso, la complessità del caso peggiore sarà O(n). Qui, la notazione "O"-big O indica la funzione di complessità.

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

Diciamo che stiamo cercando un elemento che si trova nella prima posizione dell'array. In questo scenario, l'algoritmo di ricerca lineare non cercherà tutti gli n elementi nell'array. Quindi la complessità sarà O(1). Ciò significa 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 abbiamo bisogno di memorizzare o utilizzare alcun tipo di variabile temporanea nella funzione di ricerca lineare.

Come migliorare l'algoritmo di ricerca lineare

La ricerca può essere eseguita 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 "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:

In questo metodo, scambieremo l'elemento di ricerca 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 dati [5] e dati [4]. Quindi l'array di dati sarà simile a questo:

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

Ora, se noti, più frequentemente viene cercata una chiave, più diminuisce l'indice. Pertanto, diminuendo il numero di confronti.

Spostarsi in avanti:

In questo metodo, scambiamo l'elemento di ricerca nell'indice 0. Perché se viene cercato di nuovo, possiamo trovarlo al tempo O(1).

Applicazione dell'algoritmo di ricerca lineare

Ecco alcune applicazioni di ricerca lineare che possiamo utilizzare.

• Per array di piccole dimensioni o solo per 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.