Búsqueda binaria

Dado un vector A de n elementos con valores A₀ ... A_n−1, ordenados tal que A₀ ≤ ... ≤ A_n−1, y un valor buscado T, el siguiente procedimiento usa búsqueda binaria para encontrar el índice de T en A.

1. Asignar 0 a L y a R (n − 1).
2. Si L > R, la búsqueda termina sin encontrar el valor.
3. Sea m (la posición del elemento del medio) igual a la parte entera de (L + R) / 2.
4. Si A_m < T, igualar L a m + 1 e ir al paso 2.
5. Si A_m > T, igualar R a m – 1 e ir al paso 2.
6. Si A_m = 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.[6]

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.

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.[11]

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.

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.

El arreglo de Judy usa un conjunto de ideas para lograr una solución más eficiente.

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.

Para resultados aproximados, los filtros de Bloom, otra estructura de dato probabilista basada en hashing, guarda un conjunto de valores codificando los valores con arreglos de bits y múltiples funciones de hash. Los filtros de Bloomson mucho más eficaces que los arreglos de bits en cuanto a espacio en la mayoría de los casos y mucho más lentos.[12]

Existen estructuras de datos que pueden realizar búsqueda binaria en arreglos ordenados. Por ejemplo, las búsquedas, las comparaciones parciales y todas las operaciones permitidas en arreglos ordenados pueden ser realizadas de manera más eficiente que con la búsqueda binaria con estructuras como los árboles de van Emde Boas, árboles de fusión, tries, y arreglos de bits. Sin embargo, mientras que estas operaciones pueden ser realizadas eficientemente en los arreglos ordenados sin importancia de cual sea el tipo de los elementos, este tipo de estructura de datos son usualmente más eficientes porque explotan las propiedades del conjunto de elementos del arreglo.[11]

La búsqueda binaria uniforme guarda el índice del elemento del medio y el número de elementos alrededor del elemento del medio que no hemos eliminado todavía. Cada paso reduce el tamaño del arreglo aproximadamente en la mitad. Esta variación es uniforme porque la diferencia entre los índices de los elementos del medio y el elemento escogido en la iteración anterior permanece constante para arreglos del mismo tamaño.

Búsqueda Fibonacci en la función${\displaystyle f{\bigl (}x{\bigr )}=\sin {\bigl (}{\bigl (}x+{\frac {1}{10}}{\bigr )}\pi {\bigr )}}$en el intervalo ${\displaystyle [0,1]}$. En el ejemplo anterior el algoritmo encuentra un intervalo que contiene el máximo de ${\displaystyle f}$ con una longitud menor o igual a ${\displaystyle {\frac {1}{10}}}$. En tres iteraciones, devuelve el intervalo ${\displaystyle [{\frac {5}{13}},{\frac {6}{13}}]}$, con una longitud de ${\displaystyle {\frac {1}{13}}}$.

La búsqueda Fibonacci es un método similar a la búsqueda binaria que sucesivamente reduce el tamaño del intervalo al cual el máximo de una función unimodal pertenece. Dado un intervalo finito, una función unimodal, y la máxima longitud del intervalo resultante, la búsqueda Fibonacci encuentra un número de Fibonacci tal que si el intervalo se divide en esta cantidad de subintervalos de igual longitud, los subintervalos serán menores que la máxima longitud. Después de dividido el intervalo, elimina los subintervalos a los cuales el máximo no pertenece hasta que permanezcan uno o más subintervalos continuos.[13][14]

La búsqueda exponencial es un algoritmo para buscar principalmente en listas infinitas, pero puede ser aplicada para seleccionar el límite superior de la búsqueda binaria. Comienza encontrando el primer elemento que cumple que es una potencia de dos y mayor que el valor buscado, después, fija este índice como el límite superior de la búsqueda binaria, y cambia hacia la búsqueda binaria. La búsqueda realiza ${\displaystyle \lfloor \log _{2}x+1\rfloor }$iteraciones de la búsqueda exponencial y a lo sumo ${\displaystyle \lfloor \log _{2}x\rfloor }$iteraciones de la búsqueda binaria, donde ${\displaystyle x}$ es la posición del valor buscado. Solamente si el valor buscado está cerca del principio del arreglo es que esta variación es más eficiente que seleccionar el mayor elemento como el límite superior.

Al contrario de la búsqueda binaria, la búsqueda de interpolación no calcula el punto medio sino que realiza varios intentos en busca del valor requerido, tomando en cuenta el menor y mayor elemento del arreglo así como su longitud. Este procedimiento es solamente posible si los elementos del arreglo son números. Se basa en la hipótesis de que el elemento del medio no es la mejor opción en muchos casos; por ejemplo, si el elemento buscado esta próximo al mayor elemento del arreglo, es muy probable que este ubicado en el final del arreglo. Cuando la distribución de los elementos en el arreglo es uniforme o cercanamente, se realizan ${\displaystyle O{\bigl (}\log \log n{\bigr )}}$comparaciones.[15]

En la práctica, la búsqueda de interpolación es más ineficiente que la búsqueda binaria para arreglos pequeños, dado que la búsqueda por interpolación requiere un conjunto de cómputos extras, y la tasa de crecimiento de su complejidad solo se compensa para arreglos grandes.

Cascada fraccionaria es una técnica que acelera la búsqueda binaria del mismo elemento en arreglos ordenados. La búsqueda en cada arreglo toma ${\displaystyle O{\bigl (}k\log n{\bigr )}}$, donde ${\displaystyle k}$ es el número de arreglos. Cascada fraccionaria reduce este costo a ${\displaystyle O{\bigl (}k+\log n{\bigr )}}$almacenando información específica en cada arreglo acerca de los otros arreglos.[10]

Cascada fraccionaria fue desarrollada originalmente para resolver eficientemente varios problemas de geometría computacional, pero también ha sido aplicada en dominios como el ruteo de los protocolos de internet.[10]