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: si no conoce la búsqueda binaria. geeksforgeeks.org/binary-search 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 no ha podido calcular el medio bajo correctamente pero la otra fórmula lo ha calculado correctamente. (low + high) / 2 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. para moverse hacia 2. para moverse hacia 3. (¿por qué? discutido anteriormente)4. en el ciclo while low = mid - 1 low high = mid + 1 high mid = low + ((high - low) / 2) low <= high ¿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. Cuando , 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 , no Alto permanece igual ya que es irrelevante para nuestro enunciado del problema. ¿Cómo moverse bajo y alto? array[mid] < x low = mid low = mid + 1 _¿Cómo calcular el medio?_Cuando usamos , estamos calculando el medio bajo. Entonces, cuando los #elementos en la matriz son pares, se vuelve falso, por lo que el control irá a la cláusula else donde . 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) / 2) if(array[mid] > x) low = mid mid = low + ((high - low + 1) / 2) _¿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 o . Por lo tanto, la condición en el ciclo while es . array[low] array[high] 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 para moverse bajo low = mid + 1 para moverse alto high = mid para calcular medio mid = low + ((high - low) / 2) para la condición en el bucle while low < high 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é!
