CodeUtility
Facilitiamo la vita agli sviluppatori!
Algoritmi C/C++

La ricerca lineare in C e C++

In questa lezione troverai la posizione di un valore in un array non ordinato con l'algoritmo di ricerca lineare.

Introduzione

La ricerca lineare controlla gli elementi uno per uno, dall'inizio dell'array, finché non trova il valore cercato o arriva in fondo. È l'algoritmo di ricerca più semplice e funziona anche quando i dati non sono ordinati.

Punti importanti

  • Prova con input vuoti, con un solo elemento, con valori ripetuti e già ordinati.
  • Prima fai funzionare il codice correttamente, poi ottimizza.
  • Nel codice reale preferisci le funzioni pronte della libreria standard.

Visualizzatore di La ricerca lineare in C e C++

O(n)

Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.

Esempi di codice C e C++

C
Esegui →
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));
}
Risultato dell'esecuzione
index=3
C++
Esegui →
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';
}
Risultato dell'esecuzione
index=3

Confronto tra C e C++

Entrambe le versioni hanno complessità O(n) nel caso peggiore. La funzione find in C restituisce un indice di tipo int con segno, così può usare -1 per indicare che il valore non è stato trovato. La versione in C++ usa std::find, che restituisce un iteratore: se è uguale a values.end(), il valore non è nell'array.

C

Cicli, puntatori, lunghezze e buffer temporanei sono scritti esplicitamente.

C++

Iteratori e algoritmi standard separano l'elaborazione dal modo in cui i dati sono memorizzati.

Esercizi di approfondimento

Esegui entrambe le versioni e poi modifica il codice per osservare la differenza di sicurezza che offre ciascun linguaggio.

  • Simula ogni confronto su carta.
  • Prova con valori ripetuti e con valori molto grandi e molto piccoli.
  • Misura il tempo del tuo codice e confrontalo con la libreria standard.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide