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.
Restrizioni
Rust mette già a disposizione nella sua libreria standard una
funzione di ricerca binaria.
Per questo esercizio non dovresti usare questa funzione, ma solo altri strumenti di base.
Per ottenere punti bonus
Hai fatto passare i test e hai mantenuto il codice pulito? Se vuoi, ci sono
alcune cose aggiuntive che potresti provare.
- Al momento la funzione find probabilmente funziona solo con slice di numeri,
ma il sistema di tipi di Rust è abbastanza flessibile da permettere di creare
una funzione find che funzioni su tutte le slice i cui elementi si possono
ordinare.
- Inoltre, questa funzione find può funzionare non solo sulle slice, ma allo
stesso tempo anche su un Vec o un Array.
Per eseguire i test bonus, rimuovi il flag #[ignore] ed esegui i test con la
feature generic, in questo modo:
$ cargo test --features generic
Poi condividi le tue opinioni in un commento sulla soluzione inviata. Questo
esperimento ha migliorato il codice? Peggiorato? Hai imparato qualcosa?
