Ricerca binaria

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.

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.

Comportamento

Per i casi di test, la soluzione deve corrispondere al comportamento delle funzioni searchsorted integrate in Julia. Questo significa che, invece di restituire l'indice del primo elemento corrispondente che trovi nella lista, restituirai un intervallo il cui estremo inferiore è l'indice del primo elemento corrispondente nella lista e il cui estremo superiore è l'indice dell'ultimo elemento corrispondente nella lista. Tuttavia, per semplificare la soluzione puoi assumere che l'elemento cercato non sia ripetuto, tranne che per il testset bonus sulle corrispondenze multiple.

Se l'elemento cercato non è presente nella lista, devi restituire un intervallo vuoto il cui estremo inferiore è l'indice in cui l'elemento potrebbe essere inserito nella lista ordinata. Un intervallo vuoto è qualsiasi intervallo in cui l'estremo superiore è minore dell'estremo inferiore.

Per maggiori dettagli, leggi la documentazione e gli esempi della funzione searchsorted:

searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the range of indices of a which compare as equal to x (using binary
search) according to the order specified by the by, lt and rev keywords,
assuming that a is already sorted in that order.
Return an empty range located at the insertion point if a does not contain
values equal to x.

See also: insorted, searchsortedfirst, sort, findall.

Examples

julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0

Attività bonus

• Estendi la soluzione per supportare gli argomenti per parola chiave by, lt e rev, in modo che by specifichi una trasformazione applicata a tutti gli elementi della lista, lt specifichi un confronto e rev specifichi se la lista è ordinata al contrario. Quando usi questi parametri, devi assumere che la lista sia già stata ordinata in base a essi. Per maggiori dettagli, consulta la documentazione di sort.
• Supporta le liste in cui l'elemento cercato è ripetuto (trova il primo e l'ultimo indice a cui l'elemento cercato risulta uguale).

---

Fonte

Wikipedia