Herramientas de usuario
algoritmos-oia:busqueda-binaria-separadora
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-separadora [2018/01/19 14:56] santo |
algoritmos-oia:busqueda-binaria-separadora [2025/05/01 02:46] (actual) santo [Solución trivial] |
||
|---|---|---|---|
| Línea 1: | Línea 1: | ||
| ====== Búsqueda binaria separadora ====== | ====== Búsqueda binaria separadora ====== | ||
| - | En este artículo, se discute un uso avanzado de la búsqueda binaria, para una situación particular. Es requisito entender bien la [[algoritmos-oia:busqueda-binaria|búsqueda binaria]] usual. Las ideas desarrolladas pueden servir también en otros problemas. | + | En este artículo, se discute un uso avanzado de la búsqueda binaria, para una situación muy particular. Es requisito entender bien la [[algoritmos-oia:busqueda-binaria|búsqueda binaria]] usual. Las ideas desarrolladas pueden servir también en otros problemas. |
| ==== Situación ==== | ==== Situación ==== | ||
| Línea 7: | Línea 7: | ||
| La [[algoritmos-oia:busqueda-binaria|búsqueda binaria]] "común" sirve para encontrar el "corte" en una propiedad binaria. Es decir, si tenemos una función $f$ **monótona**, que a cada entero le asigna un valor binario $0$ o $1$, búsqueda binaria sirve para encontrar el primer 1. | La [[algoritmos-oia:busqueda-binaria|búsqueda binaria]] "común" sirve para encontrar el "corte" en una propiedad binaria. Es decir, si tenemos una función $f$ **monótona**, que a cada entero le asigna un valor binario $0$ o $1$, búsqueda binaria sirve para encontrar el primer 1. | ||
| - | La situación que sea plantea aquí corresponde a encontrar los hasta $K-1$ posibles "cortes" de una función $K$-aria, es decir, que toma valores enteros en el rango $[0,K)$. Una manera de dar los cortes sería por ejemplo, dar el menor valor de $x$ tal que $f(x) \geq 1$, el menor valor de $x$ tal que $f(x) \geq 2$, y así hasta $K-1$, que es el máximo posible. | + | La situación que se plantea aquí corresponde a encontrar los hasta $K-1$ posibles "cortes" de una función $K$-aria, es decir, que toma valores enteros en el rango $[0,K)$. Una manera de dar los cortes sería por ejemplo, dar el menor valor de $x$ tal que $f(x) \geq 1$, el menor valor de $x$ tal que $f(x) \geq 2$, y así hasta $K-1$, que es el máximo posible. |
| ==== Solución trivial ==== | ==== Solución trivial ==== | ||
| Línea 13: | Línea 13: | ||
| Siempre podemos recorrer todos los $N$ valores de $x$ para buscar en una pasada todos los $K$ puntos de corte. Esto toma $O(N)$ evaluaciones de la función. | Siempre podemos recorrer todos los $N$ valores de $x$ para buscar en una pasada todos los $K$ puntos de corte. Esto toma $O(N)$ evaluaciones de la función. | ||
| - | En adelante, asumiremos siempre que $N$, la cantidad posible de valores de $x$, es bastante mayor que $K$, pues sino no hay nada considerablemente mejor que este barrido exhaustivo. | + | En adelante, asumiremos siempre que $N$, la cantidad posible de valores de $x$, es bastante mayor que $K$, pues si no no hay nada considerablemente mejor que este barrido exhaustivo. |
| ==== Solución razonable ==== | ==== Solución razonable ==== | ||
| Línea 71: | Línea 71: | ||
| </code> | </code> | ||
| - | El "valor teórico" $K \lg \left( \frac{N}{K} \right )$ en estos ejemplos da un valor $13287,7$, extremadamente cercano a lo que obtiene el método recursivo. | + | El "valor teórico" $K \lg \left( \frac{N}{K} \right )$ en estos ejemplos da un valor extremadamente cercano a lo que obtiene el método recursivo. |
| Notar que los algoritmos "directos" que hacen $K-1$ búsquedas binarias superarían en este caso al algoritmo de saltos exponenciales. Esto tiene sentido ya que cuando $K$ no es demasiado grande, realizar todas las búsquedas binarias individuales no es comparativamente tan malo. | Notar que los algoritmos "directos" que hacen $K-1$ búsquedas binarias superarían en este caso al algoritmo de saltos exponenciales. Esto tiene sentido ya que cuando $K$ no es demasiado grande, realizar todas las búsquedas binarias individuales no es comparativamente tan malo. | ||
| Línea 77: | Línea 77: | ||
| Para una corrida con valores de $K$ más extremos tendremos: | Para una corrida con valores de $K$ más extremos tendremos: | ||
| - | <code cpp> | + | <code> |
| Para N=10000000 y K=100000 | Para N=10000000 y K=100000 | ||
| Evaluaciones con saltos exponenciales : 1271222 | Evaluaciones con saltos exponenciales : 1271222 | ||
| Línea 192: | Línea 192: | ||
| Otro problema relacionado con estas ideas es [[http://ioinformatics.org/locations/ioi07/contest/day1/aliens.pdf|Aliens]], de la IOI 2007. | Otro problema relacionado con estas ideas es [[http://ioinformatics.org/locations/ioi07/contest/day1/aliens.pdf|Aliens]], de la IOI 2007. | ||
| + | |||
| + | Otro problema donde este método ayuda a realizar menos consultas y obtener más puntos es en [[https://www.oia.unsam.edu.ar/wp-content/uploads/2025/04/hormigas.pdf|Hormigas]], del Certamen de Selección 2025. | ||
| + | |||
| + | |||
algoritmos-oia/busqueda-binaria-separadora.1516373762.txt.gz · Última modificación: 2018/01/19 14:56 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
