Binary Coffee

Búsqueda Binaria

algorithms icpc
# Búsqueda Binaria La búsqueda binaria es un algoritmo *sencillo*, pero no por ello menos importante, puesto que es la base en la resolución de problemas de **Ciencias de la Computación** y **Matemáticas**. La característica más importante del algoritmo, es la optimización tanto en tiempo como en memoria. Uno de los problemas más clásicos que se resuelven con la Búsqueda Binaria, es encontrar un elemento en un listado ordenado, con una complejidad computacional logarítmica $O(logN)$. Es importante denotar que el arreglo debe estar ordenado, ya que es imprescindible que el espacio de búsqueda donde se aplique el algoritmo sea monótono (creciente o decreciente). ## Algoritmo Para entender cómo funciona se hace necesario resolver el problema de encontrar un elemento en un arreglo ordenado. Seleccionamos el elemento que se encuentra en la mitad del arreglo y comprobamos si es el que se está buscando, en el caso de ser el deseado pues damos por terminada la búsqueda, si no, se comprueba si es menor que el elemento en que se encuentra la búsqueda y por tanto significa que es necesario seguir buscando en la mitad menor a dicho elemento o en caso contrario, hacia la sección mayor. Esta operación se repite hasta que sea encontrado el elemento. Como en la operación antes descrita se va desechando la mitad del grupo de búsqueda, pues en el peor de los casos se realizan $log_2n$ como máximo para encontrar el elemento. ### Ejemplo: ![binary-search-animation](https://api.binary-coffee.dev//uploads/7e747c728e9540e680cea058f1695020.gif) ## Implementación (C++) Un error muy común en algunas implementaciones es dejar de considerar un caso límite, y es que utilizando esta fórmula $\frac{inicio+final}{2}$, es posible que en ningún momento culmine. ``` // Implentación incorrecta bool binary_search(vector<int> array, int element) { int start = 0, end = array.size() - 1; // Es posible que el ciclo nunca se detenga while( start != end ) { int middle = ( start + end ) / 2; if( array[middle] == element ) return true; else if( array[middle] > element ) end = middle; else start = middle; } return false; } ``` Una de las formas de evitar lo anterior, es considerar a la variable **inicio** un índice que siempre contiene un número menor al buscado y la variable **fin** uno mayor o igual, se detiene la búsqueda en el momento que $inicio+1$ sea igual al **fin**. Y finalmente si **arreglo[ fin ]** es diferente del número deseado, el elemento no se encuentra en el arreglo. ``` // Implementación Correcta bool binary_search(vector<int> array, int element) { int start = -1, end = array.size()-1; while( start + 1 < end ) { int middle = ( start + end ) / 2; if( array[middle] >= element ) end = middle; else start = middle; } return array[end] == element; } ``` ## Implementación con números decimales Imaginemos el siguiente sub-problema queremos buscar el menor número decimal **x** positivo para el cual la función $f(x)$ retorna **true**, se asegura que si $f(x)$ devuelve **true**, entonces $f(y)$ también devuelve **true** para toda ${y}\ge{x}$. También se asegura que $f(1e18)$ devuelve **true**. #### Solución en C++: ``` double float_binary_search() { double eps = 1e-14; double start = -1.0, end = 1e18; // llamemos eps a un valor lo suficientemente pequeño tal que start // y end se consideren prácticamente iguales while( start + eps < end ) { double middle = ( start + end ) / 2.0; if( f( middle ) ) end = middle; else start = middle; } return end; } ``` ## Problemas de práctica: [**COJ - Charlie y la Función Absoluta del Chocolate (fácil)**](http://coj.uci.cu/24h/problem.xhtml?pid=3737) [**Codeforces - Verse For Santa (fácil)**](https://codeforces.com/contest/1279/problem/B) [**Lightoj - Speed Zones (medio)**](http://lightoj.com/volume_showproblem.php?problem=1391) [**Codeforces - Minimax Problem (dificil)**](https://codeforces.com/problemset/problem/1288/D)
Opiniones