Implementar la búsqueda binaria de un arreglo

Veamos cómo pensar acerca de la búsqueda binaria en un arreglo ordenado. Sí, JavaScript ya proporciona métodos para determinar si un elemento dado está en un arreglo y, si está, dar su ubicación (así como lo hacen muchos lenguajes de programación), pero queremos implementarlo nosotros mismos, para entender cómo puedes implementar dichos métodos. Aquí hay un arreglo de JavaScript de los primeros 25 números primos, en orden:
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97];
Supón que queremos saber si el número 67 es primo. Si 67 está en el arreglo, entonces es primo.
También podemos querer saber cuántos primos son menores que 67. Si encontramos la posición del número 67 en el arreglo, podemos usar eso para averiguar cuántos primos menores existen.
La posición de un elemento en un arreglo se conoce como su índice. Los índices de los arreglos empiezan en 0 y aumentan hacia arriba. Si un elemento está en el índice 0 entonces es el primer elemento en el arreglo. Si un elemento está en el índice 3, entonces tiene 3 elementos antes que él en el arreglo.
Al mirar el siguiente ejemplo, podemos leer el arreglo de números primos de izquierda a derecha, uno a la vez, hasta que encontremos el número 67 (en la caja rosa) y ver que está en el índice 18 del arreglo. Mirar a través de los números en orden de esta manera es una búsqueda lineal.
Una vez que sabemos que el número primo 67 está en el índice 18, podemos identificar que es un primo. También podemos identificar rápidamente que hay 18 elementos que vienen antes del 67 en el arreglo, lo que significa que hay 18 números primos menores que 67.
¿Viste cuántos pasos tomó eso? Una búsqueda binaria podría ser más eficiente. Como el arreglo primes contiene 25 números, los índices en el arreglo van de 0 a 24. Al usar nuestro pseudocódigo anterior, empezamos por hacer min = 0 y max = 24. El primer intento en la búsqueda binaria sería entonces en el índice 12 (que es (0 + 24) / 2). ¿primes[12] es igual a 67? No, primes[12] es 41.
Recta numérica de la búsqueda binaria de 26 a 52
¿El índice que estamos buscando es mayor o menor que 12? Como los valores en el arreglo están en orden ascendente, y 41 < 67, el valor 67 debe estar a la derecha del índice 12. En otras palabras, el índice que estamos tratando de adivinar debe ser mayor que 12. Actualizamos el valor de min a 12 + 1, o 13, y dejamos max sin cambio en 24.
Recta numérica de la búsqueda binaria de 26 a 52
¿Cuál es el siguiente índice que intentamos? El promedio de 13 y 24 es 18.5, el cual redondeamos hacia abajo a 18, puesto que un índice de un arreglo debe ser un entero. Encontramos que primes[18] es 67.
Recta numérica de la búsqueda binaria de 26 a 52
El algoritmo de la búsqueda binaria se detiene en este punto, ya que ha encontrado la respuesta. Solo tomó dos intentos, en lugar de 19 intentos que le hubiera tomado a la búsqueda lineal. Lo puedes volver a ver paso por paso en la siguiente visualización:

Pseudocódigo

Acabamos de describir el algoritmo de la búsqueda binaria en español, haciendo cada paso en un ejemplo. Esa es una manera de hacerlo, pero una explicación en lenguaje humano puede variar en calidad. Puede ser muy corta o muy larga, y lo más importante, no siempre es tan precisa como debe ser. Podríamos adelantarnos a mostrarte la búsqueda binaria en un lenguaje de programación como JavaScript o Python, pero los programas contienen muchos detalles (debido a los requerimientos impuestos por el lenguaje de programación, o porque los programas tienen que manejar los errores causados por datos malos, errores del usuario o fallas en el sistema) que pueden hacer que sea difícil entender el algoritmo subyacente a partir de estudiar solo el código. Por eso preferimos describir los algoritmos en algo llamado pseudocódigo, que mezcla español con características que ves en los lenguajes de programación.
Aquí está el pseudocódigo para la búsqueda binaria, modificado para buscar en un arreglo. Las entradas son el arreglo, el cual llamamos array; el número n de elementos en array; y target, el número que estamos buscando. La salida es el índice de target en array:
  1. Sea min = 0 y max = n-1.
  2. Calcula guess como el promedio de max y min, redondeado hacia abajo (para que sea un entero).
  3. Si array[guess] es igual a target, entonces detente. ¡Lo encontraste! Regresa guess.
  4. Si el intento fue demasiado bajo, es decir, array[guess] < target, entonces haz min = guess + 1.
  5. De lo contrario, el intento fue demasiado alto. Haz max = guess - 1.
  6. Regresa al paso 2.

Implementar pseudocódigo

Vamos a alternar entre español, pseudocódigo y JavaScript en estas lecciones, dependiendo de la situación. Como programador, debes aprender a entender pseudocódigo y ser capaz de convertirlo en tu lenguaje de preferencia; así que aunque aquí estemos usando JavaScript, debe ser directo para ti implementar el pseudocódigo al usar otros lenguajes.
¿Cómo convertiríamos ese pseudocódigo en un programa de JavaScript? Debemos crear una función, porque estamos escribiendo código que acepta una entrada y regresa una salida, y queremos que ese código sea reutilizable para diferentes entradas. Los parámetros de la función, vamos a llamarla binarySearch, serán el arreglo y el valor objetivo, y el valor que regresa la función será el índice de la ubicación en donde se encontró el valor objetivo.
Ahora vayamos al cuerpo de la función y decidamos cómo implementar eso. El paso 6 dice regresar al paso 2. Eso suena a un bucle. ¿Debería ser un bucle for o un bucle while? Si en verdad quisieras usar un bucle for, podrías, pero los índices de los intentos de la búsqueda binaria no van en el orden secuencial que hace que un bucle for sea conveniente. Primero podemos intentar el índice 12, y luego el 18, con base en algunos cálculos. Así que un bucle while es la mejor opción.
También hay un paso importante que falta en ese pseudocódigo que no importó en el juego de adivinar, pero que sí importa para la búsqueda binaria de un arreglo. ¿Qué debería pasar si el número que estás buscando no está en el arreglo? Vamos a empezar por averiguar qué índice debería regresar la función binarySearch en este caso. Debería ser un número que no puede ser un índice válido en el arreglo. Usaremos -1, ya que no puede ser un índice válido para ningún arreglo. (En realidad, cualquier número negativo funcionaría).
El número objetivo no está en el arreglo si ya no quedan intentos posibles. En nuestro ejemplo, supón que estamos buscando el número objetivo 10 en el arreglo primes. Si estuviera ahí, el 10 estaría entre los valores 7 y 11, que están en los índices 3 y 4. Si sigues los valores de los índices para min y max a medida que se ejecuta la función binarySearch, encontrarías que eventualmente llegan al punto en donde min es igual a 3 y max es igual a 4. Entonces, el intento está en el índice 3 (ya que (3 + 4) / 2 es igual a 3.5, y redondeamos hacia abajo), y primes[3] es menor que 10, así que min se vuelve 4. Con ambos min y max iguales a 4, el intento debe estar en el índice 4, y primes[4] es mayor que 10. Ahora max se vuelve 3. ¿Qué significa que min sea igual a 4 y que max sea igual a 3? Significa que los únicos intentos posibles son por lo menos 4 y a lo más 3. ¡No hay tales números! En este punto, podemos concluir que el número objetivo, 10, no está en el arreglo primes y que la función binarySearch regresaría -1. En general, una vez que max se vuelve estrictamente menor que min, sabemos que el número objetivo no está en el arreglo ordenado. Aquí está el pseudocódigo modificado para la búsqueda binaria que maneja el caso en el cual el número objetivo no está presente:
  1. Sea min = 0 y max = n-1.
  2. Si max < min, entonces detente: target no está en array. Regresa -1.
  3. Calcula guess como el promedio de max y min, redondeado hacia abajo (para que sea un entero).
  4. Si array[guess] es igual a target, entonces detente. ¡Lo encontraste! Regresa guess.
  5. Si el intento fue demasiado bajo, es decir, array[guess] < target, entonces haz min = guess + 1.
  6. De lo contrario, el intento fue demasiado alto. Haz max = guess - 1.
  7. Regresa al paso 2.
Ahora que ya pensamos juntos en el pseudocódigo, vas a intentar implementar la búsqueda binaria. Está bien regresar y mirar el pseudocódigo; de hecho, es algo bueno, porque entonces tendrás una mejor comprensión de lo que significa convertir pseudocódigo en un programa.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.