Appunti · InformaticaIT · Maturità

Strutture dati e loro implementazione

Una struttura dati e un modo organizzato di rappresentare e conservare un insieme di dati in memoria, insieme alle operazioni che li manipolano: la scelta della struttura giusta determina la chiarezza e soprattutto l'efficienza degli algoritmi che la usano. In questo appunto si parte dai tipi strutturati statici (array, matrici, stringhe), si passa ai record e ai tipi definiti dall'utente, si studiano le strutture dinamiche lineari (liste concatenate, pile e code), si accenna alle strutture non lineari (alberi e grafi) e si chiude con gli algoritmi fondamentali di ricerca e ordinamento, valutandone il costo con la notazione asintotica.

5 sezioni~25 min di lettura3 competenzeLivello Base 2 · Standard 1 · Approfondimento 2Verificato · 07/2026

T·0333 / 14

Profilo d’esame

Scegliere e implementare la struttura dati adeguata al problema da risolvereCollegare la rappresentazione dei dati all'efficienza degli algoritmi che li elaboranoOrganizzare e manipolare insiemi di dati con strutture appropriate (lineari e non lineari)

Operatori:descrivispiegaimplementaconfrontaclassificaanalizzadeterminagiustifica

livello base

E richiesto saper riconoscere e usare gli array, le pile e le code, descrivendone le operazioni fondamentali e applicando la ricerca lineare/binaria e un ordinamento elementare.

livello avanzato

Nell'opzione Scienze Applicate si chiede di implementare le strutture in un linguaggio reale (anche le liste concatenate), di motivare la scelta della struttura sul problema e di giustificare l'efficienza degli algoritmi con la notazione asintotica O-grande.

Profondità

Testo

Contenuti · 5 sezioni

Strutture dati e loro implementazione

Array, matrici e stringhe#

BaseOSA-informatica-fondamenti-strutture-datiTipi di dato strutturati: array (vettori e matrici) e stringhe

Array di interi con indici e accesso diretto

Fig. 1Array A di 6 celle contigue in memoria; A[3] = 8 è raggiunto in un solo passo (accesso diretto, O(1)).

Un array (o vettore) e la struttura dati piu elementare: una sequenza di elementi tutti dello stesso tipo, collocati in celle di memoria contigue e individuati da un indice intero. La proprieta decisiva e l'accesso diretto (o casuale): dato l'indice i, l'elemento si raggiunge in un solo passo, perche l'indirizzo della cella si calcola con la formula indirizzo(i) = base + i x dimensione_elemento. Per questo l'accesso e l'aggiornamento di un elemento costano un tempo costante, indipendente dalla lunghezza dell'array.

L'array e una struttura statica e a dimensione fissa: la sua lunghezza n viene decisa al momento della creazione e non cambia. Gli indici, nella maggior parte dei linguaggi moderni (Python, C, Java), partono da 0 e arrivano a n-1: questo e il motivo per cui un array di n elementi ha come ultimo indice valido n-1, e accedere all'indice n e un errore (sconfinamento). La contiguita in memoria, che rende l'array velocissimo in lettura, e anche il suo limite: inserire o cancellare un elemento in mezzo costringe a spostare tutti gli elementi successivi.

Una matrice e un array bidimensionale: una tabella di righe e colonne, ottenuta concettualmente come array i cui elementi sono a loro volta array. L'elemento di riga i e colonna j si indica con M[i][j]; in memoria la matrice viene linearizzata, tipicamente per righe (row-major order), cosicche l'elemento M[i][j] di una matrice con C colonne occupa la posizione lineare i x C + j. Le matrici modellano griglie, immagini, tabelle e sistemi lineari, e si generalizzano in array a piu dimensioni.

Una stringa e, dal punto di vista della rappresentazione, un array di caratteri: ogni carattere e codificato (per esempio in Unicode/UTF-8) e occupa una posizione indicizzabile. Le operazioni tipiche sono la lettura del carattere i-esimo, il calcolo della lunghezza, la concatenazione e la ricerca di una sottostringa. Trattare la stringa come array spiega perche scorrere tutti i suoi caratteri costa un tempo proporzionale alla lunghezza, mentre leggere un singolo carattere noto e immediato.

\text{indirizzo}(i) = \text{base} + i \cdot d

Indirizzo di un elemento

In un array, l'indirizzo dell'elemento di indice i si ottiene dall'indirizzo base sommando i volte la dimensione d di un elemento: il calcolo e immediato, quindi l'accesso e a costo costante O(1).

\text{pos}(i,j) = i \cdot C + j

Linearizzazione per righe

In una matrice memorizzata per righe (row-major) con C colonne, l'elemento di riga i e colonna j occupa la posizione lineare i x C + j; gli indici partono da 0.

Esempio svolto

Indirizzo di un elemento di matrice

Una matrice M di interi ha 4 righe e 5 colonne ed e memorizzata per righe (row-major), a partire dall'indirizzo base 1000; ogni intero occupa 4 byte. Determina l'indirizzo in memoria dell'elemento M[2][3] (indici a partire da 0).

Posizione lineare
Con C = 5 colonne, la posizione lineare e pos = i x C + j = 2 x 5 + 3.
Indirizzo in byte
Si moltiplica la posizione per la dimensione d = 4 byte e si somma all'indirizzo base 1000.
Calcolo finale
13 x 4 = 52, quindi 1000 + 52 = 1052.

Risultato: L'elemento M[2][3] si trova all'indirizzo 1052; l'intera posizione si calcola con poche operazioni aritmetiche, quindi l'accesso e a costo costante O(1).

Errori frequenti

Confondere il numero di elementi (n) con l'ultimo indice (n-1) e scrivere cicli che accedono all'indice n, provocando un errore a tempo di esecuzione.
Credere che inserire un elemento in mezzo a un array sia istantaneo: in realta richiede di spostare tutti gli elementi seguenti, con costo O(n).

Approfondimento

L'array a dimensione fissa si supera in pratica con l'array dinamico (la «list» di Python, l'«ArrayList» di Java): mantiene la contiguità e l'accesso «O(1)», ma quando si riempie alloca un nuovo blocco più grande — tipicamente di capacità doppia — e vi copia gli elementi. Sebbene la singola copia costi «O(n)», raddoppiando la capacità queste riallocazioni sono rare, e l'analisi ammortizzata mostra che l'aggiunta in coda (append) costa «O(1) ammortizzato»: distribuendo il costo delle riallocazioni su tutte le operazioni, ciascuna pesa in media una costante. La contiguità offre anche un vantaggio pratico spesso decisivo: la località dei dati sfrutta la memoria cache del processore, rendendo la scansione di un array sensibilmente più veloce di quella di una lista concatenata a parità di ordine asintotico. Per le matrici la linearizzazione può essere per righe (row-major, come C e Python) o per colonne (column-major, come Fortran): scandire nell'ordine sbagliato, saltando di riga in riga anziché lungo la riga, fa perdere la località e rallenta il calcolo. Attenzione infine alle stringhe: in molti linguaggi sono immutabili, cioè ogni «modifica» crea una nuova stringa; concatenare in un ciclo n caratteri con «s = s + c» costa allora «O(n²)», perché a ogni passo si ricopia l'intera stringa accumulata — si preferisce raccogliere i pezzi in una lista e unirli una sola volta alla fine.

Ripasso attivo

Dato un array A di n numeri interi, scrivi (in pseudocodice o in un linguaggio a tua scelta) un algoritmo che calcoli la somma e il valore massimo degli elementi con una sola scansione, indicandone il costo asintotico in funzione di n.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) - Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Record e tipi di dato definiti dall'utente#

BaseOSA-informatica-fondamenti-strutture-datiRecord/strutture e tipi di dato definiti dall'utente

Record Studente: campi eterogenei sotto un unico nome

Fig. 2Un record raccoglie sotto un unico nome campi di tipo eterogeneo.

Un record (chiamato struct in C, e realizzato come classe/dataclass o namedtuple in Python e come record o classe in Java) e un tipo di dato strutturato che raggruppa sotto un unico nome piu valori, anche di tipo diverso, ciascuno identificato da un campo. Mentre l'array aggrega elementi omogenei accessibili per posizione, il record aggrega valori eterogenei accessibili per nome del campo: per esempio uno studente puo essere descritto dai campi cognome (stringa), matricola (intero) e media (reale).

Il record permette di costruire tipi di dato definiti dall'utente, cioe nuovi tipi modellati sulla realta del problema, andando oltre i tipi primitivi (intero, reale, carattere, booleano) offerti dal linguaggio. Questa astrazione e fondamentale: dare un nome unico a un'entita composta rende il programma piu leggibile, riduce gli errori e prepara il terreno alla programmazione a oggetti, dove al dato si aggiungono anche i metodi che lo manipolano (ripasso: incapsulamento).

Combinando record e array si ottengono le strutture dati che descrivono collezioni di entita: un array di record rappresenta, ad esempio, l'elenco degli studenti di una classe, dove ogni cella contiene un record con i suoi campi. L'accesso avviene in due passi: prima si seleziona l'elemento per indice (array), poi il campo per nome (record), come in elenco[i].media.

Il record e anche il mattone con cui si costruiscono le strutture dinamiche: un nodo di una lista o di un albero e tipicamente un record che contiene il valore (informazione) e uno o piu campi puntatore/riferimento ad altri nodi. La capacita di definire tipi composti e quindi il ponte tra i tipi primitivi e le strutture dati avanzate trattate nelle sezioni successive.

Esempio svolto

Media dei valori di un campo in un array di record

Dato un array elenco di N record Studente (con i campi cognome, matricola, media), scrivi un algoritmo che calcoli la media aritmetica del campo media su tutti gli studenti e indicane il costo.

Inizializzazione
Si pone un accumulatore somma a 0.
Scansione
Per i da 0 a N-1 si somma elenco[i].media all'accumulatore: si accede prima all'elemento per indice, poi al campo per nome.
Media
Al termine si divide la somma per N (con N > 0).

Risultato: L'algoritmo esegue una sola scansione dell'array, quindi ha costo lineare O(N); restituisce la media dei voti se N > 0, altrimenti il valore non e definito.

Errori frequenti

Usare array paralleli (un array per ogni attributo) al posto di un array di record, perdendo la coesione logica dell'entita e moltiplicando le occasioni di disallineamento tra gli array.
Confondere il tipo (la definizione del record, il modello) con la variabile (la singola istanza con valori concreti dei campi).

Approfondimento

Il record è il primo passo verso i tipi di dato astratti (Abstract Data Type, ADT), una delle idee più potenti dell'informatica: un ADT descrive un tipo attraverso le operazioni che vi si possono compiere e le loro proprietà (l'interfaccia, il «che cosa»), nascondendone la realizzazione interna (l'implementazione, il «come»). Pila, coda, lista, insieme e dizionario sono tutti ADT: se ne può cambiare l'implementazione — con array oppure con lista concatenata — senza toccare il codice che li usa, purché l'interfaccia resti la stessa. È l'astrazione che rende il software componibile. Il record fornisce i dati; unendovi le operazioni si arriva all'oggetto della programmazione a oggetti, dove l'incapsulamento rende l'astrazione anche protetta da usi scorretti. In memoria i campi di un record occupano celle vicine, eventualmente con qualche byte di riempimento (padding) per rispettare i vincoli di allineamento dell'architettura. Sul piano progettuale, la scelta fra «array di record» (array of structures) e «record di array» (structure of arrays, cioè array paralleli, quelli sconsigliati nei tranelli) non è solo estetica: il primo tiene insieme i dati di ciascuna entità ed è più leggibile e sicuro contro i disallineamenti; il secondo può però favorire elaborazioni che toccano un solo campo di moltissime entità. Riconoscere questo compromesso significa già ragionare da progettista di strutture dati, non da semplice utilizzatore.

Ripasso attivo

Definisci un tipo record Libro con i campi titolo (stringa), anno (intero) e prezzo (reale); dichiara poi un array di 100 libri e scrivi l'istruzione che assegna 19.90 al prezzo del terzo libro del catalogo.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) - Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Strutture dinamiche lineari: liste, pile e code#

StandardOSA-informatica-fondamenti-strutture-datiStrutture dati dinamiche e lineari: liste, pile (stack) e code (queue)

Pila (LIFO) e coda (FIFO) a confronto con le rispettive operazioni

Fig. 3Esempi: pila 3, 8, 5 (cima = 3); coda A, B, C (testa = A). La pila usa la stessa estremità per inserire ed estrarre; la coda estremità opposte.

Le strutture dinamiche superano il limite della dimensione fissa dell'array: crescono e si riducono durante l'esecuzione, allocando e liberando memoria secondo necessita. La struttura dinamica lineare fondamentale e la lista concatenata: una sequenza di nodi, dove ogni nodo e un record che contiene un'informazione e un puntatore (riferimento) al nodo successivo; l'ultimo nodo punta a nullo (NULL/None) e una variabile testa indica il primo nodo.

Nella lista concatenata i nodi non sono contigui in memoria, percio non c'e accesso diretto: per raggiungere l'i-esimo elemento occorre partire dalla testa e seguire i puntatori, con costo O(n). In compenso, inserire o cancellare un nodo del quale si conosce gia la posizione costa O(1), perche basta ridirigere uno o due puntatori senza spostare alcun dato. E qui il compromesso fondamentale: l'array privilegia l'accesso, la lista privilegia l'inserimento/cancellazione.

La pila (stack) e una struttura lineare con disciplina LIFO (Last In, First Out): l'ultimo elemento inserito e il primo a essere estratto, come in una pila di piatti. Espone solo due operazioni principali, entrambe sulla cima (top): push (inserisce un elemento in cima) e pop (rimuove e restituisce l'elemento in cima); spesso si aggiungono top/peek (leggi la cima senza rimuoverla) e isEmpty. La pila modella la valutazione delle espressioni, la gestione delle chiamate di funzione (record di attivazione) e l'annullamento delle operazioni (undo).

La coda (queue) e una struttura lineare con disciplina FIFO (First In, First Out): il primo elemento inserito e il primo a uscire, come in una fila allo sportello. Le operazioni avvengono ai due estremi: enqueue inserisce in fondo (coda), dequeue rimuove dalla testa. La coda modella tutte le situazioni di attesa ordinata: code di stampa, scheduling dei processi nel sistema operativo, buffer di comunicazione. Sia pila sia coda, se ben implementate, eseguono le loro operazioni in tempo costante O(1).

Lista concatenata: nodi (informazione + puntatore al successivo)

Fig. 4Ogni nodo contiene un’informazione e un puntatore al successivo; la testa punta al primo nodo e l’ultimo puntatore vale NULL.

Esempio svolto

Sequenza di operazioni su una pila

Una pila e inizialmente vuota. Esegui nell'ordine: push(5), push(8), pop, push(3), pop, push(7). Indica l'elemento estratto da ciascun pop e il contenuto finale della pila dalla base alla cima.

push(5), push(8)
La pila diventa, dalla base alla cima: 5, 8. La cima e 8.
pop
Si rimuove la cima: viene estratto 8 (l'ultimo inserito, LIFO). Resta: 5.
push(3)
Si inserisce 3 in cima. La pila diventa: 5, 3.
pop
Si rimuove la cima: viene estratto 3. Resta: 5.
push(7)
Si inserisce 7 in cima. La pila diventa: 5, 7.

Risultato: I pop estraggono nell'ordine 8 e poi 3; il contenuto finale della pila, dalla base alla cima, e 5, 7.

Errori frequenti

Scambiare le discipline LIFO e FIFO: estrarre dalla pila il primo elemento inserito (errato) invece dell'ultimo, o estrarre dalla coda l'ultimo invece del primo.
Perdere il riferimento alla testa o a un nodo intermedio durante un inserimento/cancellazione nella lista (ridirigere i puntatori nell'ordine sbagliato e cosi smarrire una parte della catena).

Approfondimento

La lista concatenata di base ha varianti importanti: la lista doppiamente concatenata aggiunge in ogni nodo un puntatore anche al predecessore, permettendo di scorrere in entrambi i versi e di cancellare un nodo noto in «O(1)» senza risalire la catena; la lista circolare fa puntare l'ultimo nodo al primo, utile per gestioni cicliche (turnazione round-robin). Pila e coda sono ADT implementabili sia su lista sia su array: la pila su array usa un indice «cima» che sale e scende; la coda su array conviene realizzarla come coda circolare (buffer circolare), con due indici «testa» e «coda» che avanzano modulo la capacità, così da riusare le celle liberate senza spostamenti — altrimenti ogni «dequeue» lascerebbe un buco all'inizio. Una variante utile è la deque (coda a doppia entrata), che ammette inserimenti ed estrazioni a entrambi gli estremi. L'applicazione più elegante della pila è la valutazione delle espressioni: un'espressione in notazione postfissa (polacca inversa, RPN) come «3 4 + 5 ·» si valuta scorrendola da sinistra a destra, impilando i numeri e, a ogni operatore, estraendo dalla cima i due operandi, applicando l'operazione e reimpilando il risultato — al termine la pila contiene il valore «(3+4)·5 = 35». È lo stesso identico meccanismo con cui il processore gestisce le chiamate annidate di funzione sulla pila dei record di attivazione, ciò che lega questo argomento alla ricorsione.

Ripasso attivo

Simula su carta una pila inizialmente vuota eseguendo, nell'ordine: push(5), push(8), pop, push(3), pop, push(7); indica per ogni pop l'elemento estratto e mostra il contenuto finale della pila dalla base alla cima.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) - Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Cenni alle strutture non lineari: alberi e grafi#

ApprofondimentoOSA-informatica-fondamenti-strutture-datiCenni alle strutture non lineari: alberi e grafi

Albero binario: radice, nodi interni e foglie

Fig. 5Albero binario: la radice (8) in alto, i nodi interni nel mezzo, le foglie (1, 6, 14) in basso.

Nelle strutture lineari ogni elemento ha al piu un predecessore e un successore; nelle strutture non lineari un elemento puo essere collegato a piu elementi, formando gerarchie o reti. Le due strutture non lineari fondamentali sono l'albero (gerarchia) e il grafo (rete di collegamenti generici); a livello liceale se ne studiano i concetti di base e le terminologie, senza richiedere implementazioni complesse.

Un albero e una struttura gerarchica composta da nodi collegati da archi, con un unico nodo speciale detto radice (root) da cui parte la gerarchia. Ogni nodo (tranne la radice) ha esattamente un genitore; i nodi collegati direttamente a un nodo, immediatamente sotto di esso, sono i suoi figli (i nodi raggiungibili in generale sono i suoi discendenti); i nodi senza figli sono le foglie. La profondita di un nodo e la sua distanza dalla radice, l'altezza dell'albero e la profondita massima. L'albero binario, in cui ogni nodo ha al piu due figli (sinistro e destro), e il caso piu studiato: modella espressioni, alberi di decisione e l'organizzazione gerarchica dei dati (file system, DOM di una pagina HTML).

Un grafo e un insieme di nodi (vertici) collegati da archi che rappresentano relazioni qualsiasi; a differenza dell'albero, puo contenere cicli e non ha una radice. I grafi possono essere non orientati (l'arco collega i due vertici simmetricamente) oppure orientati (l'arco ha un verso); gli archi possono inoltre essere pesati con un valore (distanza, costo, tempo). I grafi modellano reti stradali e di computer, mappe, relazioni sociali e dipendenze tra attivita.

L'albero e in realta un caso particolare di grafo: un grafo connesso e privo di cicli. Per rappresentare un grafo in memoria si usano due tecniche tipiche, la matrice di adiacenza (una tabella n x n in cui la cella indica se due vertici sono collegati) e le liste di adiacenza (per ogni vertice, la lista dei vertici a esso adiacenti): la scelta tra le due dipende dalla densita del grafo e dalle operazioni piu frequenti, ribadendo che la rappresentazione dei dati e sempre legata all'efficienza.

Esempio svolto

Lettura di un albero binario

Considera l'albero binario di radice 8 con figli 3 (sinistro) e 10 (destro), dove 3 ha i figli 1 e 6 e 10 ha il solo figlio destro 14. Individua la radice, elenca le foglie e determina l'altezza dell'albero.

Radice
La radice e il nodo da cui parte la gerarchia e che non ha genitore: e il nodo 8.
Foglie
Le foglie sono i nodi senza figli: 1, 6 e 14.
Altezza
L'altezza e la profondita massima, cioe il numero massimo di archi da radice a foglia: dal nodo 8 al nodo 6 si percorrono 2 archi (8 -> 3 -> 6).

Risultato: La radice e 8, le foglie sono 1, 6 e 14 e l'altezza dell'albero e 2.

Errori frequenti

Chiamare albero un grafo che contiene un ciclo o che ha piu di una radice: l'albero e per definizione connesso e aciclico, con un'unica radice.
Confondere la profondita di un nodo (distanza dalla radice) con l'altezza dell'albero (profondita massima), oppure scambiare nodi e foglie.

Approfondimento

Ciò che rende alberi e grafi operativi sono gli algoritmi di visita, che percorrono sistematicamente tutti i nodi. Su un albero binario si distinguono le visite in profondità — anticipata (preordine: radice, sinistro, destro), simmetrica (inordine: sinistro, radice, destro) e posticipata (postordine: sinistro, destro, radice) — e la visita in ampiezza, per livelli. La visita inordine di un albero binario di ricerca (BST), in cui per ogni nodo le chiavi del sottoalbero sinistro sono minori e quelle del destro maggiori, restituisce gli elementi già in ordine crescente. Il BST è potente perché ricerca, inserimento e cancellazione seguono un solo cammino radice-foglia: se l'albero è bilanciato (altezza «≈ log₂ n») queste operazioni costano «O(log n)», ma se degenera in una catena — per esempio inserendo dati già ordinati — l'altezza diventa «n» e il costo ricade a «O(n)»; da qui gli alberi auto-bilancianti (AVL, alberi rosso-neri). Sui grafi le due visite fondamentali sono la ricerca in ampiezza (BFS), che usa una coda e visita i vertici per distanza crescente dalla sorgente, trovando i cammini minimi in numero di archi, e la ricerca in profondità (DFS), che usa una pila (o la ricorsione) e si spinge il più lontano possibile prima di tornare indietro; entrambe toccano ogni vertice e ogni arco una sola volta, con costo «O(V + E)». Su grafi pesati il cammino di costo minimo si trova con l'algoritmo di Dijkstra, che generalizza la BFS servendosi di una coda con priorità.

Ripasso attivo

Disegna un albero binario di radice 8 con i figli 3 (sinistro) e 10 (destro), dove 3 ha come figli 1 e 6 e 10 ha il solo figlio destro 14; individua la radice, le foglie e l'altezza dell'albero.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) - Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Ricerca e ordinamento su strutture dati#

ApprofondimentoOSA-informatica-fondamenti-strutture-datiAlgoritmi fondamentali su strutture dati: ricerca (lineare, binaria) e ordinamentoCenni alla notazione asintotica per il costo degli algoritmi

Ricerca binaria di 23 su un array ordinato di 10 elementi

Fig. 6Passo 1: centro i=4 (16), 23 > 16 → scarta la metà sinistra. Passo 2: centro i=7 (56), 23 < 56 → scarta la metà destra. Passo 3: centro i=5 (23) → trovato in 3 confronti.

Le strutture dati hanno senso pieno solo insieme agli algoritmi che le elaborano: i due problemi fondamentali sono la ricerca di un elemento e l'ordinamento di una collezione. Per confrontare gli algoritmi indipendentemente dalla macchina si usa la notazione asintotica O-grande, che descrive come cresce il numero di operazioni al crescere della dimensione n dell'input, trascurando costanti e termini di ordine inferiore. Cosi O(1) e costo costante, O(log n) logaritmico, O(n) lineare, O(n log n) quasi-lineare, O(n^2) quadratico.

La ricerca lineare (sequenziale) scorre la collezione dall'inizio confrontando ogni elemento con il valore cercato finche non lo trova o non esaurisce la struttura. Funziona su qualsiasi collezione, anche non ordinata, ma nel caso peggiore esamina tutti gli n elementi: il suo costo e O(n). E l'unica ricerca possibile su una lista concatenata o su un array non ordinato.

La ricerca binaria (dicotomica) e molto piu veloce, ma richiede che l'array sia gia ordinato: confronta il valore cercato con l'elemento centrale e, sfruttando l'ordinamento, scarta ogni volta meta degli elementi rimanenti, ripetendo il procedimento sulla meta utile. Dimezzando l'intervallo a ogni passo, il costo e O(log n): su un milione di elementi bastano circa 20 confronti invece del milione della ricerca lineare. Il prezzo da pagare e mantenere l'array ordinato.

Gli algoritmi di ordinamento elementari riarrangiano gli elementi in ordine (per esempio crescente). Il selection sort cerca a ogni passo il minimo della parte non ordinata e lo porta in posizione; l'insertion sort inserisce ogni elemento nella sua posizione corretta nella parte gia ordinata; il bubble sort scambia ripetutamente coppie adiacenti fuori ordine facendo emergere il massimo a ogni passata. Tutti e tre hanno costo O(n^2) nel caso peggiore: sono semplici da capire ma poco efficienti su grandi quantita di dati, dove si ricorre ad algoritmi O(n log n) (come merge sort e quick sort). Questo legame tra struttura, ordinamento e ricerca chiarisce la competenza centrale: la rappresentazione dei dati determina l'efficienza.

T_{\text{lineare}}(n) = O(n)

Costo ricerca lineare

La ricerca sequenziale nel caso peggiore confronta tutti gli n elementi: il costo cresce linearmente con n.

T_{\text{binaria}}(n) = O(\log_2 n)

Costo ricerca binaria

Dimezzando a ogni passo l'intervallo di ricerca, il numero di confronti e dell'ordine del logaritmo in base 2 di n; richiede pero un array ordinato.

T_{\text{sort}}(n) = O(n^2)

Costo ordinamenti elementari

Selection, insertion e bubble sort confrontano nel caso peggiore un numero di coppie proporzionale a n^2: il costo cresce con il quadrato della dimensione.

Crescita del costo: confronto tra O(log n), O(n) e O(n²)

Esempio svolto

Ricerca binaria passo passo

Sull'array ordinato [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indici da 0 a 9) applica la ricerca binaria per cercare il valore 23; indica a ogni passo l'elemento centrale confrontato e conta i confronti.

Passo 1
Intervallo [0, 9]: centro all'indice (0+9)/2 = 4, valore 16. Poiche 23 > 16, si scarta la meta sinistra e si prosegue su [5, 9].
Passo 2
Intervallo [5, 9]: centro all'indice (5+9)/2 = 7, valore 56. Poiche 23 < 56, si scarta la meta destra e si prosegue su [5, 6].
Passo 3
Intervallo [5, 6]: centro all'indice (5+6)/2 = 5, valore 23. Coincide con il valore cercato: trovato all'indice 5.

Risultato: Il valore 23 viene trovato all'indice 5 in 3 confronti; coerentemente con il costo O(log n), poiche log2(10) e circa 3.32, sono sufficienti pochi confronti contro i fino a 10 della ricerca lineare.

Errori frequenti

Applicare la ricerca binaria a un array NON ordinato: il metodo presuppone l'ordinamento e su dati non ordinati puo dare risultati errati.
Confondere il caso migliore con il caso peggiore o trattare la notazione O come un tempo esatto: O descrive l'ordine di crescita, non i secondi impiegati.

Approfondimento

Vale la pena derivare esattamente i costi, non solo enunciarli. Negli ordinamenti elementari, per sistemare l'i-esimo elemento si eseguono nell'ordine di «i» confronti: il totale è «1 + 2 + ... + (n−1) = n(n−1)/2», che per n grande è dell'ordine di «n²/2», cioè «O(n²)». Il selection sort compie sempre questo numero di confronti; l'insertion sort ne fa altrettanti nel caso peggiore (dati in ordine inverso), ma solo «O(n)» sul quasi-ordinato, che è il suo caso migliore. Gli algoritmi «O(n log n)» applicano invece il paradigma «divide et impera». Il merge sort divide l'array in due metà, le ordina ricorsivamente e le fonde in tempo lineare: il suo costo obbedisce alla ricorrenza «T(n) = 2·T(n/2) + O(n)», che sviluppata produce «log₂ n» livelli, ciascuno di costo complessivo «O(n)», da cui «T(n) = O(n log n)». Il quick sort partiziona attorno a un perno (pivot): in media «O(n log n)», ma «O(n²)» nel caso peggiore, con perno sistematicamente pessimo. Due proprietà distinguono gli ordinamenti in pratica: la stabilità (un ordinamento è stabile se conserva l'ordine relativo di elementi con chiave uguale) e la memoria occupata (il merge sort richiede un array ausiliario, il quick sort ordina «sul posto»). Infine un risultato teorico notevole: nessun algoritmo di ordinamento basato su confronti può scendere sotto «O(n log n)» nel caso peggiore — è un limite inferiore «Ω(n log n)» che si dimostra contando le foglie dell'albero di decisione, poiché con n elementi le permutazioni possibili sono «n!» e servono almeno «log₂(n!) ≈ n log₂ n» confronti per distinguerle.

Ripasso attivo

Sull'array ordinato [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] applica la ricerca binaria per cercare il valore 23: indica a ogni passo l'elemento centrale confrontato, il numero totale di confronti e l'esito.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) - Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM)) · Esame di Stato del secondo ciclo - quadri di riferimento e griglie di valutazione (Ministero dell'Istruzione e del Merito (MIM))

Riferimenti e fonti

Fonti

Ministero dell'Istruzione e del Merito (MIM)

Strutture dati e loro implementazione

5 sezioni~25 min di lettura3 competenzeLivello Base 2 · Standard 1 · Approfondimento 2Verificato · 07/2026

Strutture dati e loro implementazione

Punti chiave

Indirizzo di un elemento di matrice

Punti chiave

Media dei valori di un campo in un array di record

Punti chiave

Sequenza di operazioni su una pila

Punti chiave

Lettura di un albero binario

Punti chiave

Ricerca binaria passo passo

Fonti

Strutture dati e loro implementazione

Punti chiave

Indirizzo di un elemento di matrice

Punti chiave

Media dei valori di un campo in un array di record

Punti chiave

Sequenza di operazioni su una pila

Punti chiave

Lettura di un albero binario

Punti chiave

Ricerca binaria passo passo

Fonti