Las técnicas de búsqueda lineal y binaria son las dos técnicas más fundamentales que existen en computación para encontrar un elemento particular de entre un conjunto de posibles opciones.

Empezaremos con un problema de motivación, pero finalmente veremos una manera de pensar que nos permitirá aplicar la búsqueda binaria utilizando siempre el mismo código, en otras situaciones muy distintas pero manteniendo siempre la misma idea fundamental.

Dado un arreglo ordenado de menor a mayor, sin repetidos, y un número particular que se desea buscar, determinar si el número deseado está en el arreglo o no.

Este algoritmo es muy fácil de programar, y su idea es muy simple e intuitiva. Se recorrerán todas las posiciones del arreglo, barriendo todos los candidatos posibles uno por uno. En cada uno, realizamos la verificación necesaria: Si el elemento es igual al número deseado, entonces sabemos que el número está, y podemos finalizar la ejecución. Si en cambio, luego de haber recorrido todas las posiciones, no hemos encontrado en ninguna un valor que coincida con el número buscado, entonces este no está.

El código correspondiente a este ejemplo podría ser:

bool estaEnArreglo(int numeroDeseado, const vector<int> &elementosOrdenados){
    for(int x : elementosOrdenados){
        if(x == numeroDeseado){
            return true;
        }
    }
    return false;
}

Ventajas:

• Fácil de entender y programar
• Funciona en cualquier arreglo (ordenado o no), con tan solo tener un operador de igualdad.

Desventajas

• Ineficiente: complejidad de peor caso $\Theta(N)$

La búsqueda lineal se utiliza al menos una vez en casi todos los problemas: no necesariamente aquello que estamos “buscando” es un número que se encuentra cargado en un arreglo, sino que en muchos problemas tenemos muchos “candidatos” posibles (que pueden ser casillas, argumentos a una función matemática, o cualquier otra lista de cosas), y por ejemplo queremos descubrir “el mejor” de todos ellos¹⁾, para lo cual lo que hacemos es recorrer todos y guardarnos en un acumulador el mejor hasta el momento.

En el ejemplo que acabamos de ver, nunca hemos aprovechado que el arreglo está ordenado. Ese mismo código visto funciona perfecto con cualquier arreglo, ordenado o no, pero en peor caso recorre los $n$ elementos del arreglo.

El algoritmo de búsqueda binaria se basa en aprovechar que el arreglo está ordenado, para poder descartar muchas posiciones de la búsqueda rápidamente, con una sola observación.

Si bien el objetivo final que hemos planteado en este caso es únicamente decidir si el elemento está o no está, teniendo así una salida de tipo booleano (“sí” o “no”), al considerar el problema como un problema de búsqueda, lo que queremos es encontrar el elemento, y al encontrarlo, lo encontraremos necesariamente en alguna posición del arreglo, es decir, un índice en el mismo. Por ejemplo en el arreglo $[3,7,15,19]$, el $3$ aparece en la posición $0$, el $7$ aparece en la posición $1$ y el $19$ en la posición 3.

En términos de posiciones, la búsqueda lineal que vimos antes se ocupa de probar todas las posiciones una por una, desde la $0$ hasta la $n-1$ inclusive. Esto es necesario si buscamos en un arreglo desordenado. Ahora bien, supongamos que tenemos el siguiente arreglo ordenado: $[2,10,20,50,100,150,210,1000,1005,2000]$

Supongamos que el número buscado es el $1$. Podríamos pensar en comenzar por la primera posición e ir probando todas en orden, ya que así funciona la búsqueda lineal. Pero si observamos con cuidado, al examinar la primera posición del arreglo encontraríamos un $2$, y se tiene que $1 < 2$: Estamos encontrando en la primera posición un elemento que es mayor que el que buscamos. Pero si el arreglo está ordenado, entonces todos los números que siguen también serán mayores: Al estar en orden, los de más a la derecha son más grandes, y si el $2$ ya “se pasó” del número buscado, todos los siguientes también “se pasarán”, necesariamente.

Lo anterior nos permitiría concluir luego de examinar una única posición, que el $1$ no se encuentra en el arreglo. Ya podemos ver la ganancia que produce tener el arreglo ordenado para este problema: podemos descartar muchas posiciones con una única pregunta. Podemos resumir la observación que acabamos de descubrir para nuestro problema así: Si alguna posición del arreglo se pasa, todas las siguientes se pasan, en donde “se pasa” significa que el número allí guardado es mayor que el buscado, y por lo tanto el buscado tiene que estar sí o sí a su izquierda.

Algo diferente hubiera ocurrido, sin embargo, si hubiéramos buscado el número $2018$. Como $2 < 2018$, al examinar el primer elemento del arreglo estaríamos encontrando algo menor a lo buscado, y como los números crecen hacia la derecha, concluimos que el $2018$ deberá aparecer más adelante si está. En este caso, con nuestra pregunta solamente habríamos descartado al primer $2$, y no estaríamos ganando mucho como ocurría antes. ¿Qué pasaría si en cambio decidimos examinar la última posición del arreglo? En este caso, encontraríamos un $2000$, y como $2000 < 2018$, tenemos que el $2000$ es todavía más chico que el número buscado. Como el arreglo está ordenado, a la izquierda del $2000$ los números son aún más pequeños todavía, y por lo tanto todos seguirán siendo menores que el número buscado. En este caso, examinando solamente el número del final, habríamos descartado todos y concluido que el $2018$ no se encuentra en el arreglo.

Podemos de manera similar a lo que habíamos hecho antes, resumir la observación que hicimos de la siguiente manera: Si alguna posición del arreglo se queda chica, todas las anteriores se quedan chicas , en donde “se queda chica” significa que el número allí guardado es menor que el buscado, y por lo tanto el buscado tiene que estar sí o sí a la derecha.

Hemos descubierto dos nociones distintas muy útiles, la de “pasarse” (porque las de la derecha también se pasan) y la de “quedarse chica” (porque las de la izquierda también se quedan chicas), pero en realidad son ideas opuestas, así que por comodidad nos conviene hablar de una sola. Usaremos la de pasarse.

Entonces, vamos a imaginarnos que una posición $i$ del arreglo se pasa, cuando el número allí guardado es mayor que el buscado: arreglo[i] > buscado. Si una posición $i$ se pasa, el número no puede estar en ninguna posición $j$ que sea $j \geq i$.

Lo que ya hemos observado entonces es que si una posición $i$ no se pasa (es decir, arreglo[i] <= buscado), como las que están a la izquierda tienen valores más chicos, esas tampoco se pasan. Y si una posición no se pasa, entonces el número buscado está allí o más a la derecha, es decir, no puede estar en ninguna posición $j$ que sea $j < i$.

La idea del método de búsqueda binaria es ir examinando posiciones, para ver si se pasan o no se pasan. En base a eso, podemos usar lo que sabemos para descartar muchas posiciones a la vez, y consultar solamente por las que quedan por descubrir. Surge con esta idea una pregunta natural: ¿Qué posición nos conviene examinar primero?

Vimos dos ejemplos en los cuales examinamos un elemento en un extremo del arreglo. En ambos casos ocurría lo mismo (pero con las direcciones izquierda y derecha intercambiadas): Podíamos tener suerte y resolver todo el problema en una sola pregunta, pero en el peor caso, la comparación realizada solamente nos permitía descartar este elemento extremo, teniendo que explorar aún todo el resto del arreglo. ¿Qué pasaría entonces si en lugar de consultar por un elemento en un extremo, consultamos por un elemento en la mitad del arreglo? ²⁾. En este caso, si esa posición se pasa, ya no hace falta examinar la mitad derecha, pues también se pasa. Si en cambio, esa posición central que comenzamos examinando no se pasa, entonces ya no hace falta examinar ninguna posición en la mitad izquierda del arreglo, pues tampoco se pasará. Si justo el elemento que encontramos es el que buscábamos, podríamos para la búsqueda inmediatamente si así lo deseamos.

Si continuamos de esa manera, siempre consultando un elemento central del subarreglo de elementos “desconocidos” (aquellas posiciones que aún no sabemos si se pasan o no se pasan), en cada paso descartamos la mitad de los elementos restantes. De esta manera, el total de elementos examinados será únicamente $\lceil \lg N \rceil$, que es muchísimo mejor que las $N$ consultas de la búsqueda lineal.

A continuación se puede ver un código de ejemplo que muestra esta idea. Mantendremos todo el tiempo dos posiciones especiales: la más grande conocida que no se pasa, y la más chica conocida que se pasa. Observemos que estas dos posiciones resumen toda la información que hemos conseguido hasta el momento con nuestra búsqueda³⁾.

bool estaEnArreglo(int numeroBuscado, const vector<int> &arreglo)
{
    // Guardamos siempre el mas grande que **sabemos que no se pasa**,
    //                    y el mas chico  que **sabemos que se pasa**
    // Inicialmente, no sabemos nada de ningun elemento en el arreglo,
    // asi que les ponemos los valores extremos -1 y N que estan "justo afuera".
    // Es como si el arreglo ordenado tuviera un -INF en la posicion -1, y un
    // +INF en la posicion N.
    int noSePasa = -1, sePasa = int(arreglo.size());
    while (sePasa - noSePasa > 1) // Si quedan posiciones "desconocidas", seguimos buscando
    {
        int medio = (sePasa + noSePasa)/2;
        if (arreglo[medio] == numeroBuscado)
            return true;
        else if (arreglo[medio] > numeroBuscado)
            sePasa = medio;
        else
            noSePasa = medio;
    }
    return false;
}

Hemos presentado la versión anterior de la búsqueda binaria primero, porque es una manera natural de desarrollar el tema de la forma en que deseamos mostrarla sobre el ejemplo de búsqueda en el arreglo ordenado. Este ejemplo es, por lejos, el ejemplo más común con el que se enseña y se muestra por primera vez la idea de búsqueda binaria⁴⁾, y por eso lo hemos utilizado.

Sin embargo, no es un ejemplo del caso más simple ni del más común de todos, cuando se utiliza búsqueda binaria en competencias de programación. El ejemplo anterior puede verse como un caso particular de la más compleja búsqueda binaria separadora, en que se separa en tres partes (“los menores al buscado”, “los iguales al buscado”, “los mayores al buscado”) y además se decide cortar la separación prematuramente no bien sabemos que el “rango de iguales” es no vacío.

Veremos a continuación un esquema de la búsqueda binaria más común y más simple, que es conveniente conocer y utilizar siempre que sea posible, para minimizar la chance de cometer errores en la búsqueda binaria.

El ejemplo sencillo que tomaremos como motivación será el de encontrar una pseudo-raíz-cuadrada de un número positivo dado $N$. Definimos la pseudo-raíz-cuadrada de un número positivo $N$, como el número positivo $x$ tal que $x^2 + x = N$⁵⁾.

Así, la raíz cuadrada de $4$ es exactamente $2$, pero su pseudo-raíz-cuadrada es aproximadamente $1.5615$, pues $1.5615^2 + 1.5615 \approx 4$.

Específicamente, nos mantendremos en enteros y nos alcanzará con encontrar la parte entera de la pseudo-raíz-cuadrada: Por ejemplo si nos dieran $4$ como entrada, la respuesta es $1$ porque es la parte entera de $1.5615$.

Si bien es posible utilizar observaciones matemáticas para encontrar eficientemente la respuesta (asumiendo que podemos calcular raíces cuadradas normales), si cambiáramos un poco la función (es decir la “cuenta” que estamos haciendo) habría que cambiar completamente el método. Veremos una solución con búsqueda binaria que sirve para lograr esto mismo sin asumir casi nada sobre “la cuenta” que hacemos.

Lo primero que tenemos que hacer si queremos aplicar búsqueda binaria, es identificar una propiedad binaria. ¿Qué es una propiedad binaria? Ya vimos un ejemplo antes: la noción de que una posición “se pasa”, era una propiedad binaria: hasta un cierto punto no se cumple, pero a partir de la primera posición donde se cumple, de ahí en adelante se cumple siempre.

Es decir, una propiedad binaria nos clasifica los números enteros en dos partes: Los que no cumplen la propiedad, y los que la cumplen, de manera que todos los que cumplen vienen después que todos los que no cumplen. Otra manera de decir lo mismo más resumidamente es que, si $x$ cumple la propiedad, $x+1$ también.

Por ejemplo, “ser par” no es propiedad binaria, porque los pares y los impares están todos “mezclados” en el orden de los enteros, no están todos los pares “de un lado” y todos los impares “del otro”. En cambio, “ser positivo” es una propiedad binaria.

Solamente podremos aplicar búsqueda binaria a propiedades binarias. Un error común es intentar usar búsqueda binaria en una propiedad que no lo sea. De lo que se encarga la receta de búsqueda binaria que veremos, es de encontrar los valores $a$ y $b$ “extremos” de la propiedad: es decir, aquellos tales que $b = a+1$, $a$ no cumpla la propiedad, y $b$ si la cumpla. Podemos pensar que entre $a$ y $b$ justamente estará el “corte” de la propiedad: $a$ es el más grande que no cumple, mientras que $b$ es el más chico que sí la cumple.

Para todos los problemas que se resuelven con una búsqueda binaria normal, puede plantearse una propiedad binaria, de tal manera que sabiendo $a$ y $b$ podamos hacer con ellos lo que corresponda según nuestro problema. Y es muy útil pensar los problemas de esta forma, porque entonces la misma búsqueda binaria clara y prolija podemos utilizarla en todos nuestros problemas, siempre idéntica, reduciendo así muchísimo la posibilidad de tener errores al programarla.

La forma en que programamos la búsqueda binaria para encontrar $a$ y $b$ es muy similar a lo que ya hicimos para el ejemplo previo, pues nuestra propiedad binaria en ese caso era “ser un índice $i$ tal que $arreglo[i] > x$”, siendo $x$ el número buscado: $a$ siempre será un número que no cumpla, y $b$ siempre será un número que sí cumpla. Esta es la característica fundamental de la receta, y facilita mucho recordarla y programarla sin errores:

   int a = numeroQueNoCumpla; // Depende del problema, antes fue -1
   int b = numeroQueSiCumpla; // Depende del problema, antes fue N
   while (b-a > 1) // Mientras no encontramos el "corte" de la propiedad:
   {
       int c = (a+b)/2; // Tomamos un elemento en el medio para analizar
       if (c cumple la propiedad)
          b = c; // Mantenemos la regla: b es siempre uno que cumple
       else
          a = c; // Mantenemos la regla: a es siempre uno que no cumple
   }
   // Termino la busqueda binaria y nuestros resultados listos para usar son:
   //  a : Tiene el mas grande que no cumple
   //  b : Tiene el mas chico que si cumple

Una propiedad muy útil de esta receta es que, como los elementos que se examinan son los del centro del rango, sabemos que durante la ejecución solamente se preguntará en el “if” que verifica la propiedad, por valores de $c$ que se encuentren estrictamente entre los $a$ y $b$ iniciales. En el ejemplo que vimos antes, como $a=-1$ y $b=N$, eso nos garantizaba que solamente se iba a consultar la propiedad con valores de $c$ en el rango $[0,N)$, que son los valores válidos para acceder al arreglo y entonces no había problemas de acceso fuera de rango.

¿Cómo podemos aplicar esta idea al ejemplo de calcular la pseudo-raíz-cuadrada? La cuenta $x^2+x$ justamente parte a los números en dos: Es posible que $x^2 + x > N$, o que no sea así. Si ignoramos los números negativos, que no importan para nuestro problema, como la pseudo-raíz-cuadrada exacta cumple $x^2 + x$ pero necesitamos su parte entera, tenemos que redondear hacia abajo, y por lo tanto nuestro resultado $r$ será menor o igual, teniendo $r^2 + r \leq N$.

Es decir, seguro que el $r$ que buscamos es un número tal que $r^2 + r \leq N$. Además, podemos observar que justamente el $r$ que nos dará la respuesta es el $r$ más grande que verifique esta desigualdad. Si tomamos entonces como propiedad binaria de un número $x$, que sea $x \geq 0$ y que $x^2 + x > N$, el último número que no cumpla esto será justamente la raíz (porque el primero en cumplirlo es el primero que “se pasa” estrictamente). En otras palabras, si usamos la receta con la propiedad, al terminar el valor $a$ será justamente la pseudo-raiz-cuadrada de N.

Para poder usar la receta, solamente nos falta determinar valores iniciales que cumplan y que no cumplan la propiedad. Es algo con lo que hay que tener cuidado porque cambia de problema en problema, y es un error común usar por error usar valores erróneos en la inicialización, lo que arruina toda nuestra búsqueda binaria.

En este caso, un valor inicial que podemos usar para $a$ es 0: Como el número $N$ de entrada es positivo y por definición de la pseudo-raiz-cuadrada, la parte entera buscada nunca es negativa, así que 0 nunca cumple la propiedad, ya que $0^2 + 0 = 0 \leq N$. Para $b$ hay que razonar un poco más, pero no tanto: Como para un número entero positivo $x$ siempre es $x^2 > 0$, tenemos que siempre $x^2 + x > x$, y por lo tanto $N$ es un valor que cumple (es decir, el mismo $N$ siempre se pasa de su pseudo-raiz-cuadrada), así que podemos comenzar con $b=N$⁶⁾.

Con esto en mente, copiamos la receta aplicando la propiedad de nuestro caso y nos queda:

    typedef long long tint;
    tint pseudoRaizCuadrada(tint N)
    {
        assert(N > 0);
        // La propiedad es: x >= 0 && x*x+x>N
        tint a = 0; // NO cumple la propiedad
        tint b = N; // SI cumple la propiedad
        while (b-a>1)
        {
           tint c = (a+b)/2;
           if (c*c+c > N) // c cumple la propiedad??
              b = c; // Siempre b es uno que SI cumple
           else
              a = c; // Siempre a es uno que NO cumple
        }
        return a; // Justamente, la respuesta es el ultimo que no cumple nuestra propiedad
    }

El ejemplo usa la función assert simplemente por claridad, ya que estamos asumiendo que $N>0$. Notar que no hizo falta verificar c >= 0, pues sabemos que el $a$ inicial es $0$, y entonces todos los $c$ que se examinarán en la búsqueda binaria serán mayores, o sea positivos.

Volvamos al ejemplo de programar una función que responda eficientemente si un arreglo ordenado de números contiene un valor buscado.

Para aplicar la receta, tenemos que pensar una propiedad binaria, que nos ayude a resolver el problema. La propiedad lo que hace siempre es “partir” los números en dos, los que cumplen y los que no, y nos devuelve dónde está ese “corte”. Así que necesitamos una propiedad de manera tal que el lugar donde corte, nos sirva para saber si el número está o no está.

Justamente como el arreglo está ordenado, sabemos que si el numeroDeseado aparece, todos los siguientes son mayores o iguales. En cambio, todos los anteriores son estrictamente menores ⁷⁾. Es decir, si el número está presente en el arreglo, está en el primer índice $i$ tal que $arreglo[i] \geq numeroDeseado$. Con lo cual si tomamos como propiedad “$x \geq 0$ y también $arreglo[x] \geq numeroDeseado$, o bien $x \geq N$”⁸⁾, el primer valor que cumple será la posición donde encontraremos al elemento.

Podemos verificar que la propiedad elegida es binaria: para esto basta ver que si $x$ la cumple, entonces $x+1$ también. Si $x$ la cumplía por haberse pasado del arreglo, $x+1$ también. Sino, $x$ era la posición de un elemento que ya era mayor o igual que $N$, así que al consiedar $x+1$, como el arreglo está ordenado, tendremos un número que no es más chico, y por lo tanto también será mayor o igual que $N$.

Al ser una propiedad binaria, podemos usar búsqueda binaria para encontrar los extremos (el último que no cumple, y el primero que cumple), y luego simplemente verificamos al final si el elemento buscado efectivamente está allí, en la posición donde debería estar (que es la primera que cumple).

bool estaEnArreglo(int numeroDeseado, vector<int> elementosOrdenados)
{
    const int N = int(elementosOrdenados.size());
    int low = -1; // Aca guardamos hasta donde sabemos que son menores
    int high = N; // Aca guardamos desde donde son mayores o iguales
 
    while(high-low>1)
    {
        int mid = (high+low)/2;
        if(elementosOrdenados[mid]>=numeroDeseado)
            high = mid; // Siempre high es uno que SI cumple
        else
            low = mid;  // Siempre  low es uno que NO cumple
    }
    // Como desde high sabemos que son todos mayores o iguales, si la posicion high es mayor ya esta,
    // desde aca son todos mayores y el numero no esta. Entonces si esta, esta en la posicion high.
    return high<N && elementosOrdenados[high]==numeroDeseado; // Pensar por que pedimos high<N
}

Esto que hemos hecho de encontrar “la primera posición mayor o igual que un cierto valor dado” es lo que en C++ se llama una consulta de lower_bound, y podrían utilizarse funciones ya programadas para eso (que por dentro, utilizan una búsqueda binaria como la que estamos enseñando).

A modo de ejemplo, esta misma solución utilizando el lower_bound ya existente en C++ sería:

bool estaEnArreglo(int numeroDeseado, vector<int> elementosOrdenados)
{
    // lower_bound devuelve un *iterador*, que apunta a la posicion que antes llamamos "high"
    auto it = lower_bound(elementosOrdenados.begin(), elementosOrdenados.end(), numeroDeseado);
    // Lo que antes era high<N, ahora es que el iterador no sea el .end()
    return it!=elementosOrdenados.end() && *it==numeroDeseado;
}

También se podría haber utilizado la función binary_search ya existente en C++. Conocer las funciones existentes muy útil para programar más rápido y con menos errores, pero no reemplaza saber programar nuestra búsqueda binaria, ya que no siempre nos sirve el resultado exacto de las funciones estándar, o a veces necesitamos utilizar las ideas de los algoritmos pero modificadas para nuestro caso particular.

• Setear high en $size-1$, ó low en $0$
• Hacer while(low<=high)
• Hacer $low = mid+1$, ó $low=mid-1$ en vez de $low = mid$ (lo mismo al mover el valor de high)

Para evitar estos bugs, si bien vale memorizarse la función, puede ser que se nos olvide algo, o nos confundamos. Está bueno pensar bien antes de empezar a programar la búsqueda, en qué índice estoy seguro de que se cumple la propiedad del if y en qué índice estoy seguro de que no. Además, qué pasa si se cumple en todos los elementos o en ninguno (cuáles terminan siendo los valores de low y high). En este caso por ejemplo, tuvimos que tener cuidado de verificar que sea high < N al final de la función, para evitar acceder a un elemento fuera de rango si resulta ser high == N, lo cual ocurre cuando el elemento buscado es mayor que todos los del arreglo.

Ventajas:

• Eficiente: complejidad de peor caso $\Theta(\lg N)$

Desventajas:

• Un poco más complicada de programar que la búsqueda lineal.
• Solamente funciona cuando tenemos datos “ordenados” de alguna forma:
  • Ya sea un arreglo ordenado, sobre el que buscamos valores
  • O más en general, la propiedad que estemos estudiando debe ser binaria

Supongamos que tenemos una función, ya sea una “cuenta” como en matemáticas del estilo $x^2 + 3x$, o simplemente una función como en programación: un mecanismo (o código) a partir del cual podemos obtener un valor $f(x)$ a partir de cada $x$ ⁹⁾.

El problema “directo” consiste en calcular $f(x)$, a partir de $x$, o sea computar la función. Supongamos que ese podemos resolverlo, sea porque la $f$ es una simple cuenta de matemáticas, o porque ya la tenemos programada. El problema inverso consiste en, a partir de un valor $y$ dado, encontrar un cierto $x$ para que sea $y = f(x)$. Es decir, encontrar el $x$ sabiendo el resultado que debería dar la $f$. En este sentido, hablamos de que queremos invertir la función.

Muchas veces, ocurrirá que la función es monótona. Por ejemplo, puede ser creciente, en cuyo caso si $x \leq y$, tendremos también $f(x) \leq f(y)$¹⁰⁾.

Cuando tenemos una función monótona, podemos siempre usar búsqueda binaria para invertirla: Para esto, basta considerar la propiedad $P(x) \equiv f(x) \geq y$, donde $y$ es el resultado deseado de $f$. Como la $f$ es creciente, esta propiedad es binaria: Una vez que un $x$ la cumple, tomar $x$ más grandes solamente agranda el valor de $f$, y por lo tanto se seguirá cumpliendo para siempre. Por lo tanto, podemos aplicar la técnica para encontrar el primer x que satisface $f(x) \geq y$ (por lo que sabremos que $f(x-1) < y$).

Esto no es más que otro ejemplo del lower_bound ya mencionado antes. La clave es que, si hay algún valor de $x$ donde $f(x) = y$, entonces el primero en cumplir la propiedad anterior debe ser el primero de ellos.

Exactamente esta misma idea utilizamos antes para calcular la pseudo-raíz-cuadrada: Allí estábamos utilizando búsqueda binaria para invertir la función $f$ dada por $f(x) = x^2 + x$. Notar que esta es una función monótona: no hubiéramos podido aplicar la técnica directamente para invertir, por ejemplo, la función $x^4 - 5x^3 + 10x^2 - 30x$, ya que incluso mirando solamente los $x$ positivos, esta función decrece primero pero crece luego.

Como comentario simpático pero no muy útil, todas las búsquedas binarias podemos pensarlas como un caso particular de invertir funciones: Estamos invirtiendo la función $f$ tal que $f(x) = 1$ si $x$ cumple la propiedad, y $f(x) = 0$ si $x$ no la cumple.

Si bien pueden aparecer en competencias para secundarios, los usos de búsqueda binaria con punto flotante ocurren principalmente en competencias de programación para universitarios.

Cuando trabajamos con una propiedad binaria pero en los números reales, no podemos hablar de un “último” que no cumple, ni de un “primero” que cumple, ya que en la recta numérica estos forman un continuo, y los números no tienen un anterior ni un siguiente.

Podemos sin embargo hablar de un punto de corte de la propiedad: Un cierto punto clave $c \in \mathbb{R}$, tal que ninguno de los menores a $c$ cumple la propiedad, y todos los mayores que $c$ cumplen la propiedad. El propio $c$ podría cumplir o no la propiedad, pero eso no será importante, porque de cualquier manera el método de búsqueda binaria no calcula el valor de $c$ en forma exacta.

Lo que podemos hacer es utilizar la misma receta que antes, pero utilizando números de punto flotante para las variables $a,b,c$. En lugar de terminar como antes cuando $a$ y $b$ eran “consecutivos”, la búsqueda terminará cuando $a$ y $b$ estén “suficientemente cerca”. En ese momento, sabemos que el punto de corte verdadero $c$ está en algún lugar entre $a$ y $b$, con lo cual lo tenemos determinado aproximadamente.

const double EPS = 1e-9;
double a = algoQueNoCumpla;
double b = algoQueSiCumpla;
// EPS es un double que indica cuanto error toleramos: 
// Mientras menos error, mas pasos tarda.
while (b-a > EPS) 
{
   double c = (a+b)/2.0;
   if (c cumple)
       b = c;
   else
       a = c; 
}
// El punto de corte verdadero esta entre a y b: tomamos un valor aproximado.
double corte = (a+b)/2.0;

En el paso de la búsqueda binaria, todos los ejemplos anteriores utilizaron por claridad c=(a+b)/2. Esta cuenta puede dar overflow si (a+b) puede ser muy grande, incluso cuando a y b estuvieran ambos dentro del rango de un entero de 32 o 64 bits.

Un truco que puede usarse en tales casos extremos es cambiar la cuenta por su equivalente c=a+(b-a)/2, que si estamos trabajando con números no negativos, no tendrá overflow, ya que la resta es menor que el b, que ya está entrando (suponemos) en nuestras variables. Si utilizamos números positivos y negativos en la búsqueda binaria (es menos común pero puede ocurrir), entonces dependiendo de los números es posible que este truquito no gane nada.

De cualquier manera, en la mayoría de los problemas nos evitamos estos inconvenientes de overflow utilizando long long, y no es necesario recurrir a medidas extremas (porque los números o bien “son mucho más chicos que el máximo” o bien son “mucho más grandes que el máximo”, de forma que este truquito no afecte).

Es posible utilizar búsqueda binaria para encontrar máximos y mínimos en funciones unimodales: esto se explica en este artículo.

Charla de Facundo Gutiérrez dada en el Nacional de OIA de 2017 : Charla Busqueda binaria