Búsqueda binaria en detalle

Espero que todos tengamos alguna idea de qué es y qué hace la búsqueda binaria. Pero no voy a explicar el algoritmo paso a paso, sino que voy a dar una idea de cómo funciona y cómo se puede usar la búsqueda binaria.

Consulte: geeksforgeeks.org/binary-search si no conoce la búsqueda binaria.

Dada una matriz ordenada, encontramos el elemento más central y verificamos el elemento con la clave. Si el elemento más medio es igual a clave, hemos encontrado la clave. Si el elemento más medio es mayor que la clave, buscamos en la mitad izquierda del elemento más medio, de lo contrario buscamos en la mitad derecha.

Aquí hay un código iterativo para la búsqueda binaria en Java

Note que en la línea 6, usamos

int mid = (bajo + alto) / 2;

Pero calcular mid de esta manera es ineficaz. ¿Por qué? Tomemos un ejemplo. Tomemos números enteros desde un número entero bajo hasta un número entero alto (ambos incluidos).

Observe los medios calculados por fórmulas en las columnas 3 y 4.

• 
  

  
  

  para bajo = 3 y alto = 11, el número de elementos (#elementos) = 9 Entonces solo hay 1 medio, es decir, 7* Ambas fórmulas han calculado el medio correctamente

• 
  

  
  

  para bajo = 3 y alto = 10, #elementos = 8 Así que hay 2 medios, 6 (medio inferior) y 7 (medio superior)* Ambas fórmulas han calculado el medio inferior correctamente

• 
  

  
  

  para bajo = -11 y alto = -3, #elementos = 9 Entonces solo hay 1 medio, es decir, -7* Ambas fórmulas han calculado el medio correctamente

• 
  

  
  

  para bajo = -10 y alto = -3, #elementos = 8 Así que hay 2 medios, -7 (medio bajo) y -8 (medio alto)* La fórmula (low + high) / 2 no ha podido calcular el medio bajo correctamente pero la otra fórmula lo ha calculado correctamente.

Por lo tanto, siempre debemos usar la siguiente fórmula para calcular el medio inferior, ya que es mucho más confiable:

int medio = bajo + ((alto - bajo)/2);

Cuando #elements = impar, solo tenemos 1 mid. Entonces, podemos usar la fórmula anterior para calcular el medio. Cuando #elements = even, la fórmula anterior solo da el medio inferior. El medio más alto se puede calcular mediante la siguiente fórmula:

int mid2 = bajo + ((alto - bajo + 1) / 2);

Ahora, la parte interesante…

Volvamos al código iterativo para la búsqueda binaria. Note tres cosas.1. Cómo nos estamos moviendo bajo y alto2. Cómo estamos calculando mid3. La condición en el ciclo while

La belleza de Binary Search radica solo en estas tres cosas. Exploremos esto más a fondo.

Para una búsqueda binaria simple donde solo tenemos que encontrar el elemento en la matriz, usamos lo siguiente: 1. low = mid - 1 para moverse hacia low 2. high = mid + 1 para moverse hacia high 3. mid = low + ((high - low) / 2) (¿por qué? discutido anteriormente)4. low <= high en el ciclo while

¿Es siempre el caso que usamos las mismas condiciones para la búsqueda binaria? Depende... de nuestro enunciado del problema.

Ejemplo 1:

Dado un entero x, encuentre el elemento máximo y en una matriz de tamaño N que satisfaga la condición y <= x

Solución:

Sabemos que x podría no estar en la matriz. Entonces, la búsqueda binaria simple de x en la matriz dada no funcionará. Pero para la búsqueda binaria, todo lo que sabemos es x, la clave. Necesitamos encontrar el elemento en la matriz que es el más cercano a x y menor o igual a x (si existe).

Tres cosas siempre deben venir a su mente al usar la búsqueda binaria: 1. ¿Cómo debemos movernos hacia abajo y hacia arriba?2. ¿Cómo debemos calcular mid?3. ¿Cuál sería la condición en el bucle while?

Siempre comenzamos con '¿Cómo moverse hacia abajo y hacia arriba?' y luego descubra cómo calcular mid y cuál podría ser la condición while. No al revés.

1. 
   

   
   

   
   

   
   

   ¿Cómo moverse bajo y alto? Cuando array[mid] < x , existe la posibilidad de que el elemento actual sea la respuesta (ya que y puede ser menor que x). Por lo tanto, no debemos descartar mid mientras nos movemos hacia abajo. Por lo tanto, low se convierte en low = mid , no low = mid + 1 Alto permanece igual ya que es irrelevante para nuestro enunciado del problema.

2. 
   

   
   

   
   

   _¿Cómo calcular el medio?_Cuando usamos mid = low + ((high - low) / 2) , estamos calculando el medio bajo. Entonces, cuando los #elementos en la matriz son pares, if(array[mid] > x) se vuelve falso, por lo que el control irá a la cláusula else donde low = mid . Esto da como resultado un bucle infinito. (¿Por qué? Tome un ejemplo) Por lo tanto, tomamos el medio superior, es decir, mid = low + ((high - low + 1) / 2)

3. 
   

   _¿Cuál sería la condición en el ciclo while?_Dado que estamos almacenando el elemento máximo que es menor o igual que x en low, debemos detenernos cuando low = high y devolver array[low] o array[high] . Por lo tanto, la condición en el ciclo while es low < high .

La solución en Java se ve así:

Ejemplo #2:

Dado un entero x, encuentre el elemento mínimo y en una matriz de tamaño N que satisfaga la condición y >= x

Solución:

Usando un enfoque analítico similar al que usamos en el ejemplo 1 (pruébelo usted mismo), podemos decir que

1. low = mid + 1 para moverse bajo
2. high = mid para moverse alto
3. mid = low + ((high - low) / 2) para calcular medio
4. low < high para la condición en el bucle while

Por lo tanto, podemos tabular diferentes escenarios de uso de la búsqueda binaria de la siguiente manera:

Siéntase libre de experimentar con estas condiciones y espero que haya obtenido una idea de cómo usar la búsqueda binaria.

¡Namasté!