Ricerca lineare
Ultimo aggiornamento
La ricerca lineare (detta anche ricerca sequenziale) è l'algoritmo di ricerca più semplice: parti dal primo elemento e confronti ciascuno con il valore cercato finché non trovi una corrispondenza o finiscono gli elementi. Non fa alcuna ipotesi sui dati, quindi l'array può essere non ordinato e gli elementi possono essere qualsiasi cosa confrontabile per uguaglianza.
L'animazione qui sopra evidenzia ogni confronto mentre la scansione procede da sinistra a destra e si ferma appena compare il valore cercato. La sua semplicità si paga in velocità: nel caso peggiore controlla ogni elemento, quindi richiede O(n). Quando i dati sono ordinati, la ricerca binaria trova la stessa risposta in O(log n), e se prima devi ordinare i dati, vedi il merge sort.
Complessità temporale e spaziale
| Caso | Complessità | Note |
|---|---|---|
| Caso migliore | O(1) | Il primo elemento è quello cercato. |
| Caso medio | O(n) | In media si controlla metà degli elementi prima di trovarlo. |
| Caso peggiore | O(n) | Il valore cercato è l'ultimo, oppure non c'è affatto. |
| Spazio | O(1) | Si tiene solo l'indice corrente. |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Parti dall'indice 0, il primo elemento dell'array. |
| 2 | Confronta l'elemento corrente con il valore cercato. |
| 3 | Se sono uguali, restituisci l'indice corrente (trovato). |
| 4 | Altrimenti spostati di una posizione a destra e ripeti. |
| 5 | Se arrivi alla fine dell'array senza corrispondenze, il valore non c'è (restituisci -1). |
Esempio svolto
Ricerca di 5 in [7, 3, 9, 1, 5, 8, 2]:
| Confronto | Indice | Elemento | Risultato |
|---|---|---|---|
| 1 | 0 | 7 | 7 ≠ 5: continua la scansione. |
| 2 | 1 | 3 | 3 ≠ 5: continua la scansione. |
| 3 | 2 | 9 | 9 ≠ 5: continua la scansione. |
| 4 | 3 | 1 | 1 ≠ 5: continua la scansione. |
| 5 | 4 | 5 | 5 = 5: trovato all'indice 4. |
Quando usare la ricerca lineare
| Usala quando | Evitala quando |
|---|---|
| I dati non sono ordinati o cambiano di continuo | I dati sono ordinati, quindi la ricerca binaria è esponenzialmente più veloce |
| La collezione è piccola, quindi vince la semplicità | L'insieme di dati è grande e ci cerchi più volte |
| Hai solo accesso sequenziale (stream, liste concatenate) | Puoi permetterti un indice o una tabella hash per ricerche O(1) |
Codice Linear Search
Un'implementazione di Linear Search pulita ed eseguibile in Python, JavaScript, Java, C++, C, Pseudocode. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Linear Search in Python
Python
1def linear_search(a, target):2 # Scan left to right until the target appears3 for i in range(len(a)):4 if a[i] == target:5 return i6 return -17
8
9nums = [7, 3, 9, 1, 5, 8, 2]10print("Index of 5:", linear_search(nums, 5))11print("Index of 4:", linear_search(nums, 4))Codice Linear Search in JavaScript
JavaScript
1function linearSearch(a, target) {2 // Scan left to right until the target appears3 for (let i = 0; i < a.length; i++) {4 if (a[i] === target) return i;5 }6 return -1;7}8
9const nums = [7, 3, 9, 1, 5, 8, 2];10console.log("Index of 5:", linearSearch(nums, 5));11console.log("Index of 4:", linearSearch(nums, 4));Codice Linear Search in Java
Java
1public class Main {2 static int linearSearch(int[] a, int target) {3 // Scan left to right until the target appears4 for (int i = 0; i < a.length; i++) {5 if (a[i] == target) return i;6 }7 return -1;8 }9
10 public static void main(String[] args) {11 int[] nums = {7, 3, 9, 1, 5, 8, 2};12 System.out.println("Index of 5: " + linearSearch(nums, 5));13 System.out.println("Index of 4: " + linearSearch(nums, 4));14 }15}Codice Linear Search in C++
C++
1#include <iostream>2#include <vector>3
4int linearSearch(const std::vector<int>& a, int target) {5 // Scan left to right until the target appears6 for (std::size_t i = 0; i < a.size(); i++) {7 if (a[i] == target) return static_cast<int>(i);8 }9 return -1;10}11
12int main() {13 std::vector<int> nums = {7, 3, 9, 1, 5, 8, 2};14 std::cout << "Index of 5: " << linearSearch(nums, 5) << "\n";15 std::cout << "Index of 4: " << linearSearch(nums, 4) << "\n";16 return 0;17}Codice Linear Search in C
C
1#include <stdio.h>2
3int linear_search(const int a[], int n, int target) {4 /* Scan left to right until the target appears */5 for (int i = 0; i < n; i++) {6 if (a[i] == target) return i;7 }8 return -1;9}10
11int main(void) {12 int nums[] = {7, 3, 9, 1, 5, 8, 2};13 int n = sizeof(nums) / sizeof(nums[0]);14 printf("Index of 5: %d\n", linear_search(nums, n, 5));15 printf("Index of 4: %d\n", linear_search(nums, n, 4));16 return 0;17}Codice Linear Search in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211
12FUNCTION linearSearch(target : INTEGER) RETURNS INTEGER13 DECLARE i : INTEGER14 // Scan left to right until the target appears15 FOR i ← 1 TO n16 IF nums[i] = target THEN17 RETURN i18 ENDIF19 NEXT i20 RETURN -121ENDFUNCTION22
23OUTPUT "Index of 5 is ", linearSearch(5)24OUTPUT "Index of 4 is ", linearSearch(4)Domande frequenti sulla ricerca lineare
Qual è la complessità temporale della ricerca lineare?
O(n) nel caso medio e peggiore (la scansione potrebbe dover visitare ogni elemento) e O(1) nel caso migliore, quando il primo elemento è quello cercato. Usa O(1) di spazio extra.La ricerca lineare ha bisogno di dati ordinati?
No, ed è il suo vantaggio principale. La ricerca lineare funziona su dati del tutto non ordinati perché controlla l'uguaglianza di ogni elemento; l'ordine non conta mai. La ricerca binaria, invece, funziona solo su array ordinati.
Quando la ricerca lineare è meglio della ricerca binaria?
Quando i dati non sono ordinati e li cerchi una sola volta (ordinarli prima costerebbe
O(n log n)), quando la collezione è minuscola, o quando hai solo accesso sequenziale, come in uno stream o in una lista concatenata. Per ricerche ripetute su array ordinati vince la ricerca binaria.La ricerca lineare è la stessa cosa della ricerca sequenziale?
Sì, i due nomi descrivono lo stesso algoritmo: scorrere gli elementi in sequenza finché non trovi il valore cercato o la collezione finisce.
Quanti confronti fa in media la ricerca lineare?
Se il valore c'è e può trovarsi ovunque con la stessa probabilità, circa
n/2 confronti in media; se non c'è, esattamente n. È questa crescita lineare a darle il nome di ricerca lineare.Risorse correlate
Altre visualizzazioni
