Búsqueda binaria

Instrucciones

Tu tarea es 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 reducir rápidamente las posibles ubicaciones de nuestro elemento hasta que lo encontramos, o hasta que hayamos descartado todas las ubicaciones posibles.

El algoritmo funciona así:

• Encuentra el elemento del medio de un array ordenado y compáralo con el elemento que buscamos.
• Si el elemento del medio es el que buscamos, ¡ya terminamos!
• Si el elemento del medio es mayor que el que buscamos, podemos descartar ese elemento y todos los elementos posteriores a él.
• Si el elemento del medio es menor que el que buscamos, podemos descartar ese elemento y todos los elementos anteriores a él.
• Si ya descartamos todos los elementos del array, entonces el elemento no está en el array.
• De lo contrario, repite el proceso en la parte del array que no hayas 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 del medio, 16.
• Como 23 es mayor que 16, podemos descartar la mitad izquierda del array, y nos queda [23, 28, 32].
• Después comparamos 23 con el nuevo elemento del medio, 28.
• Como 23 es menor que 28, podemos descartar la mitad derecha del array: [23].
• Encontramos el elemento que buscábamos.

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 la lista, devolverás un rango cuyo límite inferior es el índice del primer elemento coincidente de la lista y cuyo límite superior es el índice del último elemento coincidente de la lista. Sin embargo, para simplificar tu solución puedes suponer que el elemento buscado no se repite, salvo en el conjunto de pruebas de la tarea adicional sobre coincidencias múltiples.

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

Consulta 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 nombrados by, lt y rev, de modo que by especifique una transformación que se aplica a todos los elementos de la lista, lt especifique una comparación y rev indique si la lista está ordenada de forma inversa. Cuando uses estos parámetros, debes suponer que la lista ya se ordenó con ellos. Consulta la documentación de sort para obtener más detalles.
• Admite listas en las que el elemento buscado se repita (encuentra el primer y el último índice en los que el elemento buscado se compara como igual).

---

Fuente

Wikipedia