Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:busqueda-binaria [2018/01/18 22:23]
santo [Sobre búsqueda binaria con punto flotante]
+++ algoritmos-oia:busqueda-binaria [2018/01/20 14:08] (actual)
santo
@@ Línea 49: / Línea 49: @@
 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.
+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.
+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 pasan), pero en realidad son ideas opuestas, así que por comodidad nos conviene hablar de una sola. Usaremos la de pasarse.
+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$.
@@ Línea 63: / Línea 63: @@
 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 examinar mirar 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.
+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.
@@ Línea 151: / Línea 151: @@
 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$.
+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:
@@ Línea 190: / Línea 190: @@
 <code cpp>
+bool estaEnArreglo(int numeroDeseado, vector<int> elementosOrdenados)
-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){
+    while(high-low>1)
+    {
         int mid = (high+low)/2;
-        if(elementosOrdenados[mid]>=numeroDeseado){
+        if(elementosOrdenados[mid]>=numeroDeseado)
             high = mid; // Siempre high es uno que SI cumple
-        }else{
+        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,
@@ Línea 211: / Línea 211: @@
 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 ===
@@ Línea 218: / Línea 232: @@
   * 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 agregar un if al final.
+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.
@@ Línea 254: / Línea 268: @@
 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.
+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;
@@ Línea 279: / Línea 294: @@
 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 ====

OIA-Wiki

Herramientas de usuario

Herramientas del sitio

Diferencias

Herramientas de la página