Vai al contenuto principale
← OlimpiApp Facile

Informatica · Ricerca

Ricerca a salti di cinque posizioni

Un array ordinato ha 25 elementi, nelle posizioni da 1 a 25:

4, 7, 9, 12, 15, 18, 21, 25, 28, 30, 33, 36, 40,
41, 44, 47, 52, 55, 58, 60, 63, 67, 70, 74, 79

Per cercare un valore $x$ si leggono gli elementi nelle posizioni 5, 10, 15, 20, 25, in quest'ordine, fermandosi al primo maggiore o uguale a $x$; se nessuno lo è, $x$ non c'è. Altrimenti, detta $p$ la posizione in cui ci si è fermati, si leggono in ordine gli elementi dalla posizione $p-4$ alla $p$, fermandosi al primo maggiore o uguale a $x$: $x$ c'è se quell'elemento è uguale a $x$. Ogni lettura conta, anche quella di un elemento già letto.

Quale dei seguenti valori, cercato così, richiede più letture?