OIA-Wiki

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Búsqueda lineal y binaria ======

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. 

===== Problema motivador original =====

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.

==== Búsqueda lineal ====

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:

<code cpp>

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

</code>

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((El significado exacto de "el mejor" varía, lógicamente, de problema en problema, pero este esquema de búsqueda se mantiene siempre igual.)), para lo cual lo que hacemos es **recorrer todos** y guardarnos en un acumulador **el mejor** hasta el momento.

===== Búsqueda binaria =====

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? ((Si el arreglo tiene una cantidad par de elementos, hay dos elementos centrales, y podríamos tomar cualquiera de ellos)). 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((A menos que encontremos el elemento en sí, pero en ese caso esta implementación particular corta inmediatamente la búsqueda)).

<code cpp>
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;
}
</code>

==== Un esquema más general ====

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((La analogía de "buscar una palabra en el diccionario" es exactamente equivalente, pues el diccionario es el arreglo y la palabra es el número buscado.)), 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 [[algoritmos-oia:busqueda-binaria-separadora|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**.

=== Motivación ===

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$((Notemos que la raíz cuadrada normal se obtiene usando $x^2=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.

=== La receta ===

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:

<code cpp>
   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
</code>

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.

=== El ejemplo motivador con la receta ===

¿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$((También se podría haber tomado $N+1$, o $N+27$, o $3N$: Lo importante es asegurarse de empezar eligiendo **algún valor que cumpla la propiedad**)).

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

<code cpp>
    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
    }
</code>

El ejemplo usa la función [[cpp-avanzado:cassert|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.

=== El ejemplo original, pero ahora con la receta ===

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 ((Si consideramos la primera aparición del número, en caso de que aparezca varias veces)). 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$"((Considerar que todos los valores a partir de $N$, es decir que ya "se salieron" del arreglo, cumplen la propiedad, es como pensar que el arreglo ordenado "continúa para siempre" con valores "+INF")), 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).

<code cpp>
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
}
</code>

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 [[cpp-avanzado:algorithm:lower-y-upper-bound|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:

<code cpp>
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;
}
</code>

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.

=== Posibles bugs ===

  * 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.


=== Resumen de búsqueda binaria ===

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**

==== Sobre búsqueda binaria como una manera de invertir funciones monótonas ====

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$ ((En muchos problemas, la función a la cual le aplicamos esta técnica se calcula ejecutando a su vez algún otro algoritmo, como podría ser un BFS, un algoritmo goloso, un algoritmo de programación dinámica, etc)).

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)$((Si fuera decreciente, basta hacer lo mismo pero invirtiendo las comparaciones.)).

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 [[cpp-avanzado:algorithm:lower-y-upper-bound|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.
==== Sobre búsqueda binaria con punto flotante ====

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 [[cpp-avanzado:punto-flotante|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.

<code cpp>
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;
</code>
==== Sobre truquito anti-overflow ====

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).

==== Máximos y mínimos en funciones unimodales ====

Es posible utilizar búsqueda binaria para encontrar máximos y mínimos en funciones unimodales: esto se explica en [[algoritmos-oia:busqueda-ternaria|este artículo]].

==== Material adicional ====

Charla de Facundo Gutiérrez dada en el Nacional de OIA de 2017 : [[http://foro.oia.unsam.edu.ar/uploads/default/original/1X/5d40fd2f2d1dae5f44c376845ae820dfa99e5157.pdf | Charla Busqueda binaria ]]
OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Herramientas de la página
