Instalación, configuración y mantenimiento de equipos monousuario

 

Secuencial Binaria Hash Volver

Métodos de Búsqueda Binaria

El método de búsqueda binaria divide el total de los elementos en dos, comparando el elemento buscado con el central, en caso de no ser iguales, se determina si el elemento buscado es menor o mayor al central, para determinar si la búsqueda continua del lado izquierdo (menor) o derecho (mayor) del central, repitiendo el mismo proceso de división y comparación, hasta encontrar el elemento buscado o que la división ya no sea posible.

Debemos destacar que este método de búsqueda solo funciona con estructuras de datos previamente ordenadas, dividiendo cada vez a la mitad el proceso de búsqueda, lo que hace que el método sea más eficiente.

Ejemplo. Si tenemos una estructura ordenada 0, 1, 2, 3, 5, 5, 5, 7, 8, 9 y estamos buscando el número 5, el resultado de la búsqueda nos mostraría la posicione  4 y el proceso terminaría ya que el elemento buscado no es diferente al que esta en la posición central.

Elementos

0

1

2

3

5

5

5

7

8

9

Posiciones

0

1

2

3

4

5

6

7

8

9

Posiciones donde

encontró el número 5

i

 

 

 

√

 

 

 

 

F

Este proceso debe sumar la posición inicial y la final, dividiendo el resultado de la suma entre dos para obtener la posición central generada por el cociente de la división, en este caso es (0+9)/2 = 4, esta posición se compara con el elemento que estamos buscando y como son iguales la búsqueda se detiene mostrando la posición donde lo encontró.

Ejercicio. Crear un programa que aplique una búsqueda binaria de un dato dentro de un arreglo de elementos ordenados y presenta la posición donde encontró el dato.

¿Podemos hacer algo mejor? Trataremos de aprovechar el hecho de que la lista está ordenada y vamos a hacer algo distinto: nuestro espacio de búsqueda se irá achicando a segmentos cada vez menores de la lista original. La idea es descartar segmentos de la lista donde el valor seguro que no puede estar:

  1. Consideramos como segmento inicial de búsqueda a la lista completa.
  2. Analizamos el punto medio del segmento (el valor central), si es el valor buscado, devolvemos el índice del punto medio.
  3. Si el valor central es mayor al buscado, podemos descartar el segmento que está desde el punto medio hacia la a derecha.
  4. Si el valor central es menor al buscado, podemos descartar el segmento que está desde el punto medio hacia la izquierda.
  5. Una vez descartado el segmento que no nos interesa, volvemos a analizar el segmento restante, de la misma forma.
  6. Si en algún momento el segmento a analizar tiene longitud 0 o negativa significa que el valor buscado no se encuentra en la lista.

Para señalar la porción del segmento que se está analizando a cada paso, utilizaremos dos variables (izq y der) que contienen la posición de inicio y la posición de fin del segmento que se está considerando. De la misma manera usaremos la varible medio para contener la posición del punto medio del segmento.

En el gráfico que se incluye a continuación, vemos qué pasa cuando se busca el valor 18 en la lista [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23].

Figura 8.1 Cómo funciona la búsqueda de un elemento dentro del array

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:

 

Volver