Diferencias

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

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