Búsqueda binaria

Instrucciones

Tu tarea consiste en implementar un algoritmo de búsqueda binaria.

Un algoritmo de búsqueda binaria encuentra un elemento en un array dividiéndolo repetidamente por la mitad y conservando solo la mitad que contiene el elemento que buscamos. Nos permite acotar rápidamente las posibles ubicaciones de nuestro elemento hasta que lo encontremos o hasta que hayamos descartado todas las posibles ubicaciones.

El algoritmo funciona así:

• Busca el elemento central de un array ordenado y compáralo con el elemento que buscamos.
• Si el elemento central es nuestro elemento, ¡hemos terminado!
• Si el elemento central es mayor que nuestro elemento, podemos descartar ese elemento y todos los elementos posteriores a él.
• Si el elemento central es menor que nuestro elemento, podemos descartar ese elemento y todos los elementos anteriores a él.
• Si se han descartado todos los elementos del array, el elemento no está en el array.
• En caso contrario, repite el proceso en la parte del array que no se haya descartado.

Aquí tienes un ejemplo:

Supongamos que buscamos el número 23 en el siguiente array ordenado: [4, 8, 12, 16, 23, 28, 32].

• Empezamos comparando 23 con el elemento central, 16.
• Como 23 es mayor que 16, podemos descartar la mitad izquierda del array, con lo que nos queda [23, 28, 32].
• A continuación, comparamos 23 con el nuevo elemento central, 28.
• Como 23 es menor que 28, podemos descartar la mitad derecha del array: [23].
• ¡Hemos encontrado nuestro elemento!

Comportamiento

Tu solución debe coincidir con el comportamiento de las funciones searchsorted integradas de Julia para los casos de prueba. Esto significa que, en lugar de devolver el índice del primer elemento coincidente que encuentres en el array, devolverás un rango cuyo límite inferior es el índice del primer elemento coincidente del array y cuyo límite superior es el índice del último elemento coincidente del array. No obstante, para simplificar tu solución puedes suponer que el elemento objetivo no se repite, salvo en el conjunto de pruebas de la tarea adicional sobre coincidencias múltiples.

Si el elemento buscado no está en el array, debes devolver un rango vacío cuyo límite inferior sea el índice en el que podría insertarse el elemento en el array ordenado. Un rango vacío es cualquier rango en el que el límite superior sea menor que el límite inferior.

Lee la documentación y los ejemplos de la función searchsorted para obtener más detalles:

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

Tareas adicionales

• Amplía tu solución para admitir los argumentos de palabra clave by, lt y rev, de modo que by especifique una transformación aplicada a todos los elementos del array, lt especifique una comparación y rev especifique si el array está ordenado en orden inverso. Cuando se usan estos parámetros, debes suponer que el array ya se ha ordenado con ellos. Consulta la documentación de sort para obtener más detalles.
• Admite arrays en los que el elemento objetivo se repite (encuentra el primer y el último índice que coinciden con el elemento objetivo).

---

Fuente

Wikipedia