Herramientas de usuario
algoritmos-oia:busqueda-binaria
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
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. | 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: | Con esto en mente, copiamos la receta aplicando la propiedad de nuestro caso y nos queda: | ||
| Línea 190: | Línea 190: | ||
| <code cpp> | <code cpp> | ||
| - | + | bool estaEnArreglo(int numeroDeseado, vector<int> elementosOrdenados) | |
| - | bool estaEnArreglo(int numeroDeseado, vector<int> elementosOrdenados){ | + | { |
| const int N = int(elementosOrdenados.size()); | const int N = int(elementosOrdenados.size()); | ||
| int low = -1; // Aca guardamos hasta donde sabemos que son menores | int low = -1; // Aca guardamos hasta donde sabemos que son menores | ||
| int high = N; // Aca guardamos desde donde son mayores o iguales | int high = N; // Aca guardamos desde donde son mayores o iguales | ||
| | | ||
| - | while(high-low>1){ | + | while(high-low>1) |
| + | { | ||
| int mid = (high+low)/2; | int mid = (high+low)/2; | ||
| - | if(elementosOrdenados[mid]>=numeroDeseado){ | + | if(elementosOrdenados[mid]>=numeroDeseado) |
| high = mid; // Siempre high es uno que SI cumple | high = mid; // Siempre high es uno que SI cumple | ||
| - | }else{ | + | else |
| low = mid; // Siempre low es uno que NO cumple | 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, | // 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). | 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 === | === 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). | 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 ==== | ==== Material adicional ==== | ||
algoritmos-oia/busqueda-binaria.1516333272.txt.gz · Última modificación: 2018/01/19 03:41 por guty
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
