Vai al contenuto
Topos Uranos
Italiano

Cercare e ordinare

Riepilogo

Cercare e ordinare sono i due problemi fondamentali sulle collezioni, e tra loro c’è uno scambio: ordinare una volta costa, ma rende più economica ogni ricerca successiva. La lezione scrive a mano la ricerca lineare e quella binaria, che su dati ordinati scarta la metà a ogni passo; giustifica la binaria con il suo invariante, dimostra che termina, ne conta le iterazioni e studia i tre errori che la rovinano. Seguono l’ordinamento per selezione e quello per inserimento, con i loro invarianti e il conteggio esatto dei loro confronti; poi gli stessi problemi con la libreria ranges, e il calcolo che decide quando conviene ordinare prima di cercare.

Obiettivi di apprendimento

  1. Implementare la ricerca lineare e quella binaria, e giustificare la binaria con il suo invariante («se il valore c’è, sta tra low e high»), con la dimostrazione che termina.
  2. Implementare l’ordinamento per selezione e per inserimento, enunciare l’invariante di ciascuno e contarne i confronti nel caso migliore e nel caso peggiore.
  3. Usare std::ranges::sort, std::ranges::contains, std::ranges::find, std::ranges::binary_search e std::ranges::lower_bound al posto delle versioni proprie quando è opportuno, rispettandone le precondizioni.
  4. Decidere, in base al numero di ricerche previste, se conviene ordinare i dati prima di cercarvi, e giustificare la decisione con il conteggio dei confronti.

Ricerca lineare

Cercare significa rispondere, data una collezione e un valore, se il valore c’è e dove. Senza informazioni sull’ordine dei dati, non c’è altra strategia che guardarli uno per uno: è la ricerca lineare. Quando il valore non c’è, questo corso restituisce values.size(), la prima posizione che non appartiene al vettore: non è un indice valido, così non si confonde con una risposta, ed è la stessa convenzione che segue la libreria, come si vedrà nella quinta sezione.

Programma in C++
#include <cstddef>#include <print>#include <vector>​// Precondizione: nessuna.// Postcondizione: restituisce il minimo indice i con values[i] == target,// oppure values.size() se target non è presente.std::size_t linearSearch(const std::vector<int>& values, int target){    // Invariante: target non è in values[0], ..., values[i - 1].    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}: non presente", target);        } else {            std::println("{}: posizione {}", target, pos);        }    }}
Output
207: posizione 3112: posizione 1999: non presente

L’invariante della riga 10 dà la correttezza. All’inizio, con i uguale a 0, afferma qualcosa su un tratto vuoto ed è vero. Se vale all’inizio di un’iterazione e values[i] non è il valore cercato, vale alla fine con un elemento in più. Ora, il ciclo ha due uscite: se return i; viene eseguita, values[i] è il valore cercato e, per l’invariante, nessun elemento precedente lo era, da cui i è la prima occorrenza (per questo il 112, che compare due volte, viene indicato nella posizione 1); se il ciclo termina per la condizione, i vale values.size() e l’invariante dice che il valore non è da nessuna parte. Il return dentro il ciclo termina la funzione, e con essa il ciclo, e risparmia un flag.

Il costo, nel senso della lezione Il costo di un algoritmo, si misura con i confronti values[i] == target. Se il valore non c’è, se ne fanno esattamente nn, uno per elemento: il caso peggiore. Se è nella posizione pp, se ne fanno p+1p + 1. La ricerca lineare è, dunque, O(n)O(n): con il doppio dei dati, il doppio del lavoro. Senza informazioni aggiuntive non si può fare meglio: un algoritmo che tralasciasse di guardare un elemento non saprebbe se il valore era lì.