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 04:42] 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 49: | Línea 49: | ||
| Entonces, lo que haremos en esta versión del algoritmo será **siempre preguntar por el elemento central**. La idea quizás es menos clara ahora, pues en lugar de ir incrementalmente "corte por corte", para aprovechar siempre toda la información que tenemos y no repetir preguntas innecesarias, lo que conviene es calcular **todos los cortes** en la misma función recursiva. | Entonces, lo que haremos en esta versión del algoritmo será **siempre preguntar por el elemento central**. La idea quizás es menos clara ahora, pues en lugar de ir incrementalmente "corte por corte", para aprovechar siempre toda la información que tenemos y no repetir preguntas innecesarias, lo que conviene es calcular **todos los cortes** en la misma función recursiva. | ||
| - | Supongamos por ejemplo, que tenemos $K=10$ y comenzamos consultando el elemento central, y es $f(c) = 7$. ¿Qué nos dice esto? Nos dice inmediatamente que las primeras apariciones de $8$ y $9$ estarán **a la derecha de $c$**, mientras que las primeras apariciones de $0$,$1$,$2$,$\dots$,$7$ estarán entre $0$ y $c$ inclusive. En otras palabras, el rango de $10$ cortes a analizar que teníamos se nos **separa** en dos: 8 cortes deben ser analizados del lado izquierdo, y 9 cortes deben ser analizados del lado derecho. Lo que hacemos es, recursivamente, analizar cada una de estas mitades de la misma forma, pero sabiendo que allí la función solamente puede tomar valores en un **subrango** de los $K$ posibles valores totales. | + | Supongamos por ejemplo, que tenemos $K=10$ y comenzamos consultando el elemento central, y es $f(c) = 7$. ¿Qué nos dice esto? Nos dice inmediatamente que las primeras apariciones de $8$ y $9$ estarán **a la derecha de $c$**, mientras que las primeras apariciones de $0$,$1$,$2$,$\dots$,$7$ estarán entre $0$ y $c$ inclusive. En otras palabras, el rango de $10$ cortes a analizar que teníamos se nos **separa** en dos: 8 cortes deben ser analizados del lado izquierdo, y 2 cortes deben ser analizados del lado derecho. Lo que hacemos es, recursivamente, analizar cada una de estas mitades de la misma forma, pero sabiendo que allí la función solamente puede tomar valores en un **subrango** de los $K$ posibles valores totales. |
| Supongamos que analizamos el caso derecho, por ejemplo: Allí, sabemos que la función solo puede tomar valores $7$, $8$ y $9$, y nos interesa descubrir la primera aparición de $8$ y de $9$ (la primera de 7 no, porque sabemos que apareció antes, ya que una llamada recursiva "nos llamó" habiendo descubierto un valor $7$ a nuestra izquierda). Preguntamos como siempre en la mitad de nuestro rango: ¿Qué pasaría si encontramos un $7$? Sabríamos inmediatamente que la mitad izquierda no sirve para nada, y podemos ignorarla quedando solamente con la mitad derecha, y los mismos valores posibles $7,8,9$. Es decir, en tal caso **reducimos el problema a la mitad**. Lo mismo hubiera ocurrido si hubiéramos encontrado un $9$: La mitad derecha resultaría inútil, y en la izquierda seguiríamos buscando los mismos dos cortes. | Supongamos que analizamos el caso derecho, por ejemplo: Allí, sabemos que la función solo puede tomar valores $7$, $8$ y $9$, y nos interesa descubrir la primera aparición de $8$ y de $9$ (la primera de 7 no, porque sabemos que apareció antes, ya que una llamada recursiva "nos llamó" habiendo descubierto un valor $7$ a nuestra izquierda). Preguntamos como siempre en la mitad de nuestro rango: ¿Qué pasaría si encontramos un $7$? Sabríamos inmediatamente que la mitad izquierda no sirve para nada, y podemos ignorarla quedando solamente con la mitad derecha, y los mismos valores posibles $7,8,9$. Es decir, en tal caso **reducimos el problema a la mitad**. Lo mismo hubiera ocurrido si hubiéramos encontrado un $9$: La mitad derecha resultaría inútil, y en la izquierda seguiríamos buscando los mismos dos cortes. | ||
| 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.1516336946.txt.gz · Última modificación: 2018/01/19 04:42 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
