Algoritmos de búsqueda binaria explicados usando C ++

La búsqueda binaria es uno de esos algoritmos con los que te encontrarás en cada (buena) clase de introducción a la informática. Es un algoritmo eficaz para encontrar un elemento en una lista ordenada . Por el bien de este ejemplo, asumiremos que se trata de una matriz.

Los objetivos de la búsqueda binaria son:

  • ser capaz de descartar la mitad de la matriz en cada iteración
  • minimizar la cantidad de elementos que tenemos que atravesar
  • déjanos un valor final

Tomemos, por ejemplo, la siguiente matriz de enteros:

int array[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 };

Digamos que estamos tratando de encontrar el valor de índice del número 7 en esta matriz. Hay 17 elementos en total y los valores del índice van de 0 a 16.

Podemos ver que el valor de índice de 7 es 4, ya que es el quinto elemento de la matriz.

Pero, ¿cuál sería la mejor manera para que la computadora encuentre el valor índice del número que estamos buscando?

Primero, almacenamos los valores miny max, como 0y 16.

int min = 0;int max = 16;

Ahora tenemos que hacer una suposición. Lo más inteligente sería adivinar un valor de índice en el medio de la matriz.

Con el valor de índice de 0 a 16 en esta matriz, el valor de índice medio de esta matriz sería 8. Eso contiene el número 14.

// This will round down if the quotient is not an integer

int guess = (min + max) / 2;

Nuestra suposición ahora es igual a 8, que es 14 en la matriz, ya que array[8]es igual a 14.

Si el número que estábamos buscando fuera 14, ¡habríamos terminado!

Dado que ese no es el caso, ahora descartaremos la mitad de la matriz. Estos son todos los números después del 14, o el valor del índice 8, ya que sabemos que 14 es mayor que 7 y nuestra estimación es demasiado alta.

Después de la primera iteración, nuestra búsqueda ahora está dentro de: 1, 3, 4, 6, 7, 8, 10, 13

No tenemos que adivinar en la última mitad de la matriz original, porque sabemos que todos esos valores son demasiado grandes. Por eso es importante que apliquemos la búsqueda binaria a una lista ordenada .

Dado que nuestro cálculo original de 14 era mayor que 7, ahora lo disminuimos en 1 y lo almacenamos en max:

max = guess - 1; // max is now equal to 7, which is 13 in the array

Ahora la búsqueda se ve así:

 1, 3, 4, 6, 7, 8, 10, 13
min = 0max = 7guess = 3 

Debido a que nuestra suposición fue demasiado baja, descartamos la mitad inferior de la matriz aumentando el min, a la inversa de lo que hicimos anteriormente para max:

min = guess + 1; // min is now 4

En la siguiente iteración, nos quedamos con:

 7, 8, 10, 13min = 4max = 7guess = 5

Dado que el valor del índice 5 devuelve 8, ahora estamos uno por encima de nuestro objetivo. Repetimos el proceso nuevamente, y nos quedamos con:

 7min = 4max = 4guess = 4

Y nos quedamos con un solo valor, 4, como índice del número objetivo que estábamos buscando, que era 7.

El propósito de la búsqueda binaria es deshacerse de la mitad de la matriz en cada iteración. Así que solo trabajamos en aquellos valores en los que tiene sentido seguir adivinando.

El pseudocódigo para este algoritmo se vería así:

  1. Vamos min = 0, y vamos max = ndonde nes el valor de índice más alto posible
  2. Encuentre el promedio de miny max, redondee hacia abajo para que sea un número entero. Este es nuestroguess
  3. Si adivinamos el número, detente, ¡lo tenemos!
  4. Si guesses demasiado bajo, establezca minigual a uno más deguess
  5. Si guesses demasiado alto, establezca maxigual a uno menos queguess
  6. Vuelve al paso dos.

Aquí hay una solución, escrita en C ++: