Algoritmo de búsqueda binaria

Algoritmo de búsqueda binaria 

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.

¿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.

¿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.

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: