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
Non sminuirti usando la libreria standard di strumenti per le collezioni. Puoi e dovresti completare questo esercizio senza strumenti come Array.tryFindIndex.
Suggerimenti
Per questo esercizio tornano utili le seguenti funzionalità di F#:
-
Ricorsione in coda Previeni gli stack overflow con input di grandi dimensioni usando la ricorsione in coda. Anche se non ci sono casi di test che lo verificano esplicitamente, usare la ricorsione in coda porta a una soluzione più performante. Un'altra buona risorsa sulla ricorsione in coda è questo post del blog.
-
Pattern matching è estremamente potente e aiuta a semplificare la logica condizionale a più rami.
