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 15:07] santo |
algoritmos-oia:busqueda-binaria [2018/01/20 14:08] (actual) santo |
||
---|---|---|---|
Línea 190: | Línea 190: | ||
<code cpp> | <code cpp> | ||
- | |||
bool estaEnArreglo(int numeroDeseado, vector<int> elementosOrdenados) | bool estaEnArreglo(int numeroDeseado, vector<int> elementosOrdenados) | ||
{ | { | ||
Línea 212: | 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 281: | 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 ==== |