Algoritmo di ricerca

Un algoritmo di ricerca è un algoritmo che permette di trovare un elemento avente determinate caratteristiche all'interno di un insieme di elementi.

Funzionamento

Gli elementi dell'insieme sono caratterizzati da una chiave e da un gruppo di dati satellite. Nella descrizione degli algoritmi di ricerca, i dati satellite vengono tipicamente ignorati perché non sono utilizzati nella ricerca. La chiave è quell'insieme di valori che identifica un elemento dell'insieme. Ha un ruolo fondamentale perché un algoritmo ricerca quell'elemento che possiede una certa chiave.

La chiave può avere un qualsiasi tipo di dato e può anche essere formata da un insieme di valori: dipende dal tipo di insieme che si vuole rappresentare. La chiave può essere univoca in tutto l'insieme di elementi, oppure multipla qualora sia consentito di condividerla tra più elementi distinti. In questo secondo caso è fondamentale specificare il corretto comportamento di un algoritmo di ricerca. Bisogna infatti decidere se sarà restituito il primo elemento dotato di una certa chiave, l'ultimo, uno qualsiasi o anche tutti.

Tabella di simboli

Una tabella di simboli è una struttura dati formata da un record con chiave che supporta due operazioni di base: inserimento di un nuovo record e ricerca di un record avente una data chiave. La tabella di simboli viene spesso chiamata dizionario per l'analogia che ha con esso. Questo tipo di struttura permette di avere molta dinamicità sui dati con possibilità di modifiche elastiche nel tempo. Molti metodi di ricerca costruiscono strutture dati che consentono efficienti operazioni di ricerca basate proprio su questo concetto di tabella di simboli^{[senza fonte]}. L'ottimizzazione di algoritmi di ricerca è molto importante in ambito informatico.