Ricerca lineare vs binaria
Ricerca lineare vs binaria è un esperimento interattivo di Algoritmi in azione, una simulazione gratuita di StudyFi Lab che funziona direttamente nel browser.
La ricerca lineare controlla gli elementi uno alla volta, quindi nel caso peggiore servono n passi: O(n). La ricerca binaria funziona solo su un array ordinato: guarda al centro e, a seconda del risultato, scarta un’intera metà. Dopo ogni passo resta al massimo la metà, quindi bastano al più ⌈log₂(n+1)⌉ passi: O(log n). Con 40 elementi sono 6 passi invece di 40.
Prova questo: Imposta 40 elementi e cerca l’ultimo valore. Poi scegli un numero che non è nell’array: quanti passi servono a ciascuna ricerca per accorgersene?
Domande frequenti
Che cosa mostra l’esperimento «Ricerca lineare vs binaria»?
La ricerca lineare controlla gli elementi uno alla volta, quindi nel caso peggiore servono n passi: O(n). La ricerca binaria funziona solo su un array ordinato: guarda al centro e, a seconda del risultato, scarta un’intera metà. Dopo ogni passo resta al massimo la metà, quindi bastano al più ⌈log₂(n+1)⌉ passi: O(log n). Con 40 elementi sono 6 passi invece di 40.
Come provo «Ricerca lineare vs binaria»?
Imposta 40 elementi e cerca l’ultimo valore. Poi scegli un numero che non è nell’array: quanti passi servono a ciascuna ricerca per accorgersene?
Studi per una verifica?
Carica i tuoi appunti e StudyFi li trasforma in flashcard, test e podcast.