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 [2018/01/19 15:02] (actual) santo [Búsqueda binaria separadora] |
||
---|---|---|---|
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 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 |