En ciencias de la computación y matemáticas, la búsqueda binaria, también conocida, como búsqueda de intervalo medio o búsqueda logarítmica, es un algoritmo de búsqueda que encuentra la posición de un valor en un array ordenado. Compara el valor con el elemento en el medio del array, si no son iguales, la mitad en la cual el valor no puede estar es eliminada y la búsqueda continúa en la mitad restante hasta que el valor se encuentre.
La búsqueda binaria es computada en el peor de los casos en un tiempo logarítmico, realizando comparaciones, donde n es el número de elementos del arreglo y log es el logaritmo. La búsqueda binaria requiere solamente O(1) en espacio, es decir, que el espacio requerido por el algoritmo es el mismo para cualquier cantidad de elementos en el array. Aunque estructuras de datos especializadas en la búsqueda rápidas como las tablas hash pueden ser más eficientes, la búsqueda binaria se aplica a un amplio rango de problemas de búsqueda.
Aunque la idea es simple, implementar la búsqueda binaria correctamente requiere atención a algunos detalles como su condición de parada y el cálculo del punto medio de un intervalo.
Existen numerosas variaciones de la búsqueda binaria. Una variación particular (cascada fraccional) acelera la búsqueda binaria para un mismo valor en múltiples arreglos.
Algoritmo La búsqueda binaria funciona en arreglos ordenados. La búsqueda binaria comienza por comparar el elemento del medio del arreglo con el valor buscado. Si el valor buscado es igual al elemento del medio, su posición en el arreglo es retornada. Si el valor buscado es menor o mayor que el elemento del medio, la búsqueda continua en la primera o segunda mitad, respectivamente, dejando la otra mitad fuera de consideración.
Procedimiento Dado un vector A de n elementos con valores A0 ... An−1, ordenados tal que A0 ≤ ... ≤ An−1, y un valor buscado T, el siguiente procedimiento usa búsqueda binaria para encontrar el índice de T en A. Asignar 0 a L y a R (n − 1). Si L > R, la búsqueda termina sin encontrar el valor. Sea m (la posición del elemento del medio) igual a la parte entera de (L + R) / 2. Si Am < T, igualar L a m + 1 e ir al paso 2. Si Am > T, igualar R a m – 1 e ir al paso 2. Si Am = T, la búsqueda terminó, retornar m. Este procedimiento iterativo mantiene los límites de la búsqueda mediante dos variables. Algunas implementaciones realizan la comparación de igualdad al final del algoritmo, como resultando se obtiene un ciclo más rápido de comparaciones pero se aumenta en uno la cantidad de iteraciones promedio.Bottenbruch, Hermann (1962).
Coincidencias aproximadas El procedimiento anterior solo realiza coincidencias exactas, encontrando la posición del valor buscado. Sin embargo, dado el orden natural de los arreglos ordenados, es trivial extender la búsqueda binaria para realizar coincidencias aproximadas. Por ejemplo, la búsqueda binaria puede ser usada para computar, para un valor dado, su rank (el número de elementos menores), antecesor (próximo elemento menor), sucesor (próximo elemento mayor), y vecinos cercanos. Las consultas en intervalos, como por ejemplo, buscar el número de elementos entre dos números pueden ser computadas con dos preguntas de rank. Las consultas de rank pueden ser realizadas usando una modificación de la búsqueda binaria, retornando m en las búsquedas donde se encuentre el elemento, y L en donde no se encuentre, correspondiendo este último al número de elementos menores que el valor buscado. Las consultas de antecesor y sucesor pueden ser computadas con preguntas de rank también. Una vez que el rank del valor buscado es conocido, su antecesor es el elemento en la posición dado por su rank(el elemento mayor que es menor que el valor buscado). Su sucesor es el elemento después del (si él está presente en el arreglo) o en la posición siguiente al antecesor (en otro caso). El vecino más cercano del valor buscado es su antecesor o su sucesor, de los dos el más cercano. Las consultas de rango son también fáciles de manipular. Una vez que los rank de ambos valores son conocidos, el número de elementos mayores o iguales al primer valor y menores que el segundo es la diferencia de los dos ranks. Esta cantidad puede disminuir o aumentar de acuerdo si los extremos del intervalo deben ser considerados parte de la pregunta en cuestión y cuando el arreglo contenga llaves que coincidan con los extremos.
Rendimiento miniaturadeimagen|Un árbol que representa el algoritmo de búsqueda binaria. El arreglo en el cual se usa el algoritmos es [20, 30, 40, 50, 90, 100], y el valor buscado es 40. El rendimiento de la búsqueda binaria puede ser analizada reduciendo el algoritmo a un árbol binario de búsqueda, donde la raíz es el elemento en el medio del arreglo, el elemento en el medio de la primera parte del arreglo es el hijo izquierdo de la raíz y el elemento en el medio de la segunda parte es el hijo derecho de la raíz. El resto del árbol se construye de forma similar. Este modelo representa a la búsqueda binaria, comenzando desde la raíz, el subárbol izquierdo o derecho son recorridos de acuerdo a si el valor buscado es menor o mayor que el valor presente en el nodo actual, representando la eliminación sucesiva de los elementos.Flores, Ivan; Madpis, George (1971).
En el peor de los casos se realizan iteraciones (del ciclo de comparaciones), donde la notación denota la parte entera por debajo de la función. Esta cantidad de iteraciones es alcanzada cuando la búsqueda alcanza el nivel más profundo del árbol, equivalente a una búsqueda binaria que se reduce a un solo elemento, y en cada iteración, siempre elimina el arreglo más pequeño de los dos si no tienen la misma cantidad de elementos.
Como promedio, asumiendo que cada elemento es igualmente probable de ser buscado, después que la búsqueda termine, el valor buscado será más probable de ser encontrado en el segundo nivel del árbol. Esto es equivalente a una búsqueda binaria que completa una iteración antes del peor de los casos, alcanzándola después de iteraciones. Sin embargo, el árbol puede estar no balanceado, con el nivel más profundo parcialmente completo, y equivalentemente, el arreglo puede no estar dividido perfectamente por la búsqueda en algunas iteraciones, resultando que en la mitad de las veces el menor subarreglo es eliminado. El promedio actual del número de iteraciones es ligeramente mayor . En el mejor de los casos, donde el elemento del medio del arreglo es igual al valor buscado, su posición es retornada después de una iteración. En términos de iteración, ningún algoritmo basado solamente en comparaciones puede exhibir mejores promedios en su número de iteraciones que la búsqueda binaria.
Cada iteración de la búsqueda binaria definida anteriormente realiza una o dos comparaciones, comprobando si el elemento en el medio es igual al valor buscado en cada iteración. Asumiendo nuevamente que cada elemento es igualmente probable de ser buscado, cada iteración realiza como promedio 1.5 de comparaciones. Una variación del algoritmo comprueba por la igualdad en el final de cada búsqueda, eliminando como promedio la mitad de las comparaciones en cada iteración. En la mayoría de las computadoras el procedimiento anterior reduce el tiempo de cada iteración muy poco, mientras que garantiza que la búsqueda realice el mayor número de iteraciones posibles y como promedio adiciona una iteración más a la búsqueda. Dado que el ciclo de comparaciones se realiza solamente veces en el peor de los casos, para un n suficientemente grande, el pequeño incremento de la eficiencia producto de las comparaciones en el ciclo no compensa la iteración extra. Knuth 1998 propuso un valor de (más de 76 trillones) elementos para que esta variación fuese más rápida.Sloane, Neil.Rolfe, Timothy J. (1997).
Cascada fraccional puede ser usada para acelerar la búsqueda del mismo valor en múltiples arreglos. Se requiere para buscar en cada arreglo el elemento seleccionado, cascada fraccional lo reduce a , donde k es el número de arreglos.Chazelle, Bernard; Liu, Ding (2001).
Comparación de la búsqueda binaria con otros esquemas La técnica de usar arreglos ordenados con búsqueda binaria es una solución muy ineficiente cuando la inserción y la eliminación son necesarias, tomando un tiempo de
Otros algoritmos soportan más eficientemente la inserción y la eliminación, y también un macheo más rápido y exacto.
Hashing Para implementar arreglos asociativos, tablas hash, una estructura que mapea llaves contra valores usando una función de hash, son generalmente más rápidas que la búsqueda binaria en arreglos ordenados de valores; la mayoría de las implementaciones requiere como promedio un tiempo amortizado constante. Sin embargo, hashing no es muy útil para comparaciones aproximadas, tales como antecesor, sucesor, y vecino más cercano, dado que la información que nos presenta en la búsqueda es si el valor está presente o no. La búsqueda binaria es ideal para este tipo de comparaciones, realizándolas en tiempo logarítmico.Beame, Paul; Fich, Faith E. (2001).
Árboles Un árbol binario de búsqueda es una estructura de datos que funciona basado en el principio de la búsqueda binaria: los valores del árbol están colocados en forma ordenada, y el recorrido del árbol es realizado usando un algoritmo muy parecido a la búsqueda binaria. La inserción y eliminación requieren al igual que el recorrido un tiempo logarítmico. Este costo es mucho mejor que el costo lineal de la inserción y eliminación en los arreglos ordenados, y los árboles de búsqueda binaria poseen la habilidad de realizar todas las operaciones posibles en los arreglos ordenados, incluyendo consultas en rangos y comparaciones aproximadas.
Sin embargo, la búsqueda binaria es usualmente más eficiente para realizar búsquedas puesto que los árboles binarios de búsqueda estarán probablemente desbalanceados, dando como consecuencia un costo computacional superior a la búsqueda binaria.
Los árboles binarios de búsqueda se utilizan para realizar búsquedas rápidas en dispositivos de almacenamientos externos, donde los datos necesitan ser buscados y colocados en la memoria principal. Dividiendo el árbol en páginas con una cantidad determinada de elementos resultado que la búsqueda en el árbol binario tenga un menor costo computacional que los buscadores convencionales de los discos. Note que este proceso crea un árbol multipropósito, puesto que cada página está conectada una con otra. El árbol-B generaliza este método de la organización en el árbol, los Arbol-B son frecuentemente utilizados para organizar largos conjuntos de datos como las bases de datos o los sistemas de ficheros.
Búsqueda lineal La búsqueda lineal es un simple algoritmo de búsqueda que comprueba cada elemento hasta que encuentre el valor buscado. La búsqueda lineal puede ser implementada en una lista enlazada, que nos permite inserciones y eliminaciones más eficientes que un arreglo. La búsqueda binaria es más eficiente que la búsqueda lineal en los arreglos ordenados, exceptuando los arreglos que contenga pocos elementos. Si el arreglo debe ser ordenado primero, ese costo debe ser amortizado sobre cualquier búsqueda. Ordenar el arreglo también nos permite comparaciones aproximadas más eficientes, entre otras operaciones.
Aproximaciones mixtas El arreglo de Judy usa un conjunto de ideas para lograr una solución más eficiente.
Algoritmos de clasificación Un problema relacionado con la búsqueda es la clasificación. Cualquier algoritmo que realice búsquedas, como la búsqueda binaria, puede ser usado para clasificar también. Existen otros algoritmos más específicos para la clasificación, un arreglo de bit es el más simple, usado cuando el rango de los elementos es limitado, es muy rápido ya que requiere un tiempo constante.