Introduzione
Hai incontrato un gruppo di matematici che sono anche cantautori.
Hanno scritto una canzone per ciascuno dei loro numeri preferiti e, come puoi immaginare, hanno un sacco di numeri preferiti (come 0 o 73 o 6174).
Sei curioso di sentire la canzone del tuo numero preferito, ma con così tante canzoni da setacciare, trovare quella giusta potrebbe richiedere un po' di tempo.
Per fortuna, hanno organizzato le loro canzoni in una playlist ordinata per titolo, che poi è semplicemente il numero di cui parla la canzone.
A questo punto ti rendi conto che puoi usare un algoritmo di ricerca binaria per trovare rapidamente una canzone a partire dal titolo.
Istruzioni
Il tuo compito è implementare un algoritmo di ricerca binaria.
Un algoritmo di ricerca binaria trova un elemento in un array dividendolo ripetutamente a metà e tenendo solo la metà che contiene l'elemento che stiamo cercando.
Ci permette di restringere rapidamente le possibili posizioni del nostro elemento finché non lo troviamo, o finché non abbiamo eliminato tutte le posizioni possibili.
La ricerca binaria funziona solo se l'array è ordinato.
L'algoritmo funziona così:
- Trova l'elemento centrale di un array ordinato e confrontalo con l'elemento che stiamo cercando.
- Se l'elemento centrale è quello che cerchiamo, abbiamo finito!
- Se l'elemento centrale è maggiore di quello che cerchiamo, possiamo eliminare quell'elemento e tutti gli elementi successivi.
- Se l'elemento centrale è minore di quello che cerchiamo, possiamo eliminare quell'elemento e tutti gli elementi precedenti.
- Se ogni elemento dell'array è stato eliminato, allora l'elemento non è presente nell'array.
- Altrimenti, ripeti il procedimento sulla parte dell'array che non è stata eliminata.
Ecco un esempio:
Supponiamo di cercare il numero 23 nel seguente array ordinato: [4, 8, 12, 16, 23, 28, 32].
- Iniziamo confrontando 23 con l'elemento centrale, 16.
- Dato che 23 è maggiore di 16, possiamo eliminare la metà sinistra dell'array, e ci rimane
[23, 28, 32].
- Confrontiamo poi 23 con il nuovo elemento centrale, 28.
- Dato che 23 è minore di 28, possiamo eliminare la metà destra dell'array:
[23].
- Abbiamo trovato l'elemento che cercavamo.
Messaggi di eccezione
A volte è necessario sollevare un'eccezione. Quando lo fai, dovresti sempre includere un messaggio di errore significativo che indichi qual è l'origine dell'errore. Questo rende il codice più leggibile ed aiuta molto nel debug. Quando sai che l'origine dell'errore sarà di un certo tipo, puoi scegliere di sollevare uno dei tipi di errore predefiniti, ma dovresti comunque includere un messaggio significativo.
Questo esercizio in particolare richiede che tu usi la istruzione raise per «lanciare» un ValueError quando il valore dato non si trova nell'array. I test passeranno solo se sollevi l'exception con raise e ci alleghi un messaggio.
Per sollevare un ValueError con un messaggio, scrivi il messaggio come argomento del tipo di exception:
# example when value is not found in the array.
raise ValueError("value not in array")
