Ricerca lineare
La ricerca lineare controlla gli elementi fino al match o alla fine.
Che cos’è Ricerca lineare?
La ricerca lineare controlla gli elementi fino al match o alla fine.
Trova un target in dati non ordinati.
Punti importanti
- Testa input vuoti, singoli, duplicati e ordinati.
- Separa correttezza e ottimizzazione.
- Preferisci la standard library in produzione.
Visualizzatore di Ricerca lineare
O(n)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Esempi di codice C e C++
main.c
#include <stdio.h>
int find(const int *values, int size, int target) {
for (int index = 0; index < size; ++index) {
if (values[index] == target) return index;
}
return -1;
}
int main(void) {
int values[] = {14, 3, 27, 8, 19};
printf("index=%d\n", find(values, 5, 8));
}
index=3C++
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector values{14, 3, 27, 8, 19};
auto match = std::find(values.begin(), values.end(), 8);
std::cout << "index="
<< std::distance(values.begin(), match) << '\n';
}
index=3Confronto tra C e C++
Entrambe sono O(n) nel caso peggiore. C restituisce -1; C++ restituisce un iteratore confrontato con end.
C
Loop, puntatori, dimensioni e buffer sono espliciti.
C++
Iteratori e algoritmi separano operazione e storage.
Esercizi pratici
Esegui entrambe le versioni e modificale per osservare le diverse garanzie.
- Traccia ogni confronto.
- Testa duplicati e valori estremi.
- Confronta con la standard library.