Algoritmos III: Búsqueda binaria

Bienvenido a la tercera parte de la colección de Algoritmos de Ciencias de la Computación. Una vez más, profundizaremos en la recursión al abordar el tema de las búsquedas binarias.

Una "búsqueda binaria" es un algoritmo de búsqueda que se utiliza en un arreglo que ya está ordenado. Compara el valor objetivo con el elemento central de un arreglo. Si no coinciden, se ignora la mitad en la que el objetivo no puede estar y la búsqueda continúa en la mitad restante, tomando nuevamente el elemento central para compararlo con el valor objetivo y repitiendo este proceso hasta encontrarlo. Si el valor objetivo no está contenido en el arreglo, con el tiempo los índices de búsqueda izquierdo y derecho se cruzarán, y esa condición debe terminar la búsqueda.

Algoritmo

Para simplificar, llamaré al arreglo "arr", al índice inicial "left", al índice final "right" y al elemento que buscamos "elem". Inicialmente, los valores de entrada para left y right serán left = 0 y right = sizeOfArray - 1. El resto del algoritmo puede dividirse en cinco pasos:

1. Si "left" > "right", la búsqueda debe terminar sin éxito.
2. Establece el índice central como la división entera hacia abajo de ("left" + "right") / 2.
3. Si arr(middle) < "elem", establece "left" = middle + 1 y reinicia el algoritmo.
4. Si no, si arr(middle) > "elem", establece "right" = middle - 1 y reinicia el algoritmo.
5. De lo contrario, arr(middle) == "elem" y se ha encontrado el elemento que buscas.

Instrucciones

La función recursiva de este desafío utilizará una búsqueda binaria para encontrar un elemento en un arreglo dado. Si el elemento ingresado se encuentra, la función debe devolver true. Si no logra encontrarlo, debe devolver false.

Ejemplos

binarySearch([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], left, right, 7) ➞ True

binarySearch([1, 11, 14, 15, 32, 64, 67, 88, 92, 94], left, right, 12) ➞ False

binarySearch([3, 6, 9, 12, 15, 18, 21, 24, 27, 30], left, right, 27) ➞ True

Notas

• El arreglo será un arreglo de enteros y todos los enteros serán positivos.
• Varios de los desafíos que se cubrirán en esta colección sobre algoritmos pueden resolverse sin recursión y sin implementar los algoritmos descritos en cada desafío. Les pido a quienes resuelvan estos desafíos que lo hagan según lo previsto. No comprender los conceptos enseñados será un obstáculo para los desafíos posteriores y no ayudará a nadie a avanzar en sus habilidades como programador.
• Si te atascas, consulta la pestaña Resources, la pestaña Comments o, si estás realmente atascado, usa la pestaña Solutions para desbloquear las respuestas.