Búsqueda binaria

comparaciones, donde n es el número de elementos del arreglo y log es el logaritmo.

Una variación particular (cascada fraccional) acelera la búsqueda binaria para un mismo valor en múltiples arreglos.

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.

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.

Este procedimiento iterativo mantiene los límites de la búsqueda mediante dos variables.

[6]​ El procedimiento anterior solo realiza coincidencias exactas, encontrando la posición del valor buscado.

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.

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.

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.

[8]​[9]​ Cascada fraccional puede ser usada para acelerar la búsqueda del mismo valor en múltiples arreglos.

para buscar en cada arreglo el elemento seleccionado, cascada fraccional lo reduce a

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.

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.

Ordenar el arreglo también nos permite comparaciones aproximadas más eficientes, entre otras operaciones.

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.

[12]​ Existen estructuras de datos que pueden realizar búsqueda binaria en arreglos ordenados.

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.

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.

Cuando la distribución de los elementos en el arreglo es uniforme o cercanamente, se realizan

Cascada fraccionaria es una técnica que acelera la búsqueda binaria del mismo elemento en arreglos ordenados.

En 1986, Bernard Chazelle y Leonidas J. Guibas introdujeron cascada fraccional, una técnica usada para acelerar la búsqueda binaria en múltiples arreglos.

[18]​ En una implementación práctica, las variables utilizadas para representar los índices a menudo serán de tamaño fijo, y esto puede dar lugar a un desbordamiento aritmético para arreglos muy grandes.

Un problema similar ocurrirá si el valor buscado es menor que el menor valor en el arreglo y el primer índice del arreglo es el valor representable más pequeño de R. En particular, esto significa que R no debe ser un tipo sin signo si el arreglo empieza con índice 0.. Un bucle infinito puede ocurrir si las condiciones de salida para el bucle no están definidas correctamente.

Además, el bucle debe salir cuando se encuentra el elemento de destino, o en el caso de una implementación donde este control se mueve al final, comprueba si la búsqueda tuvo éxito o falló al final debe estar en su lugar.