Diferencias

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

--- algoritmos-oia:busqueda-binaria [2018/01/19 03:23]
guty [Búsqueda binaria]
+++ algoritmos-oia:busqueda-binaria [2018/01/20 14:08] (actual)
santo
@@ 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 280: / 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