Búsqueda binaria

Search algorithm finding the position of a target value within a sorted array

En informática , la búsqueda binaria , también conocida como búsqueda de medio intervalo , ^[1] búsqueda logarítmica , ^[2] o corte binario , ^[3] es un algoritmo de búsqueda que encuentra la posición de un valor objetivo dentro de una matriz ordenada . ^{[4] [5]} La búsqueda binaria compara el valor objetivo con el elemento central de la matriz. Si no son iguales, se elimina la mitad en la que no puede estar el objetivo y la búsqueda continúa en la mitad restante, tomando nuevamente el elemento del medio para comparar con el valor objetivo y repitiendo esto hasta que se encuentre el valor objetivo. Si la búsqueda termina con la mitad restante vacía, el objetivo no está en la matriz.

La búsqueda binaria se ejecuta en tiempo logarítmico en el peor de los casos , haciendo comparaciones, donde es el número de elementos en la matriz. ^{[a] [6]} La búsqueda binaria es más rápida que la búsqueda lineal excepto para matrices pequeñas. Sin embargo, la matriz debe ordenarse primero para poder aplicar la búsqueda binaria. Hay estructuras de datos especializadas diseñadas para búsquedas rápidas, como tablas hash , que se pueden buscar de manera más eficiente que la búsqueda binaria. Sin embargo, la búsqueda binaria se puede utilizar para resolver una gama más amplia de problemas, como encontrar el siguiente elemento más pequeño o el siguiente más grande en la matriz en relación con el objetivo, incluso si está ausente de la matriz. ${\displaystyle O(\log n)}$ ${\displaystyle n}$

Existen numerosas variantes de la búsqueda binaria. En particular, la búsqueda en cascada fraccionaria acelera las búsquedas binarias del mismo valor en múltiples matrices. La búsqueda en cascada fraccionaria resuelve de manera eficiente una serie de problemas de búsqueda en geometría computacional y en muchos otros campos. La búsqueda exponencial extiende la búsqueda binaria a listas ilimitadas. Las estructuras de datos de árbol de búsqueda binaria y árbol B se basan en la búsqueda binaria.

Algoritmo

La búsqueda binaria funciona en matrices ordenadas. La búsqueda binaria comienza comparando un elemento en el medio de la matriz con el valor objetivo. Si el valor objetivo coincide con el elemento, se devuelve su posición en la matriz. Si el valor objetivo es menor que el elemento, la búsqueda continúa en la mitad inferior de la matriz. Si el valor objetivo es mayor que el elemento, la búsqueda continúa en la mitad superior de la matriz. Al hacer esto, el algoritmo elimina la mitad en la que el valor objetivo no puede estar en cada iteración. ^[7]

Procedimiento

Dada una matriz de elementos con valores o registros ordenados de tal manera que , y el valor objetivo , la siguiente subrutina utiliza la búsqueda binaria para encontrar el índice de en . ^[7] ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle A_{0},A_{1},A_{2},\ldots ,A_{n-1}}$ ${\displaystyle A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle A}$

1. Establecer en y en . ${\displaystyle L}$ ${\displaystyle 0}$ ${\displaystyle R}$ ${\displaystyle n-1}$
2. Si es así , la búsqueda finaliza porque no tuvo éxito. ${\displaystyle L>R}$
3. Establezca (la posición del elemento del medio) en el piso de , que es el mayor entero menor o igual a . ${\displaystyle m}$ ${\displaystyle {\frac {L+R}{2}}}$ ${\displaystyle {\frac {L+R}{2}}}$
4. Si , configúrelo en y vaya al paso 2. ${\displaystyle A_{m}<T}$ ${\displaystyle L}$ ${\displaystyle m+1}$
5. Si , configúrelo en y vaya al paso 2. ${\displaystyle A_{m}>T}$ ${\displaystyle R}$ ${\displaystyle m-1}$
6. Ahora la búsqueda está hecha; regresa . ${\displaystyle A_{m}=T}$ ${\displaystyle m}$

Este procedimiento iterativo lleva un registro de los límites de búsqueda con las dos variables y . El procedimiento puede expresarse en pseudocódigo de la siguiente manera, donde los nombres y tipos de las variables siguen siendo los mismos que antes, es la función de piso y hace referencia a un valor específico que transmite el error de la búsqueda. ^[7] ${\displaystyle L}$ ${\displaystyle R}$floorunsuccessful

búsqueda binaria

La función binary_search(A, n, T) es L := 0 R := n − 1 mientras L ≤ R lo haga m := piso((L + R) / 2) si A[m] < T entonces L := m + 1 De lo contrario, si A[m] > T entonces R := m − 1 De lo contrario : devolver m retorno fallido

Como alternativa, el algoritmo puede tomar el límite de . Esto puede cambiar el resultado si el valor objetivo aparece más de una vez en la matriz. ${\displaystyle {\frac {L+R}{2}}}$

Procedimiento alternativo

En el procedimiento anterior, el algoritmo verifica si el elemento del medio ( ) es igual al objetivo ( ) en cada iteración. Algunas implementaciones omiten esta verificación durante cada iteración. El algoritmo realizaría esta verificación solo cuando quede un elemento (cuando ). Esto da como resultado un bucle de comparación más rápido, ya que se elimina una comparación por iteración, mientras que solo requiere una iteración más en promedio. ^[8] ${\displaystyle m}$ ${\displaystyle T}$ ${\displaystyle L=R}$

Hermann Bottenbruch publicó la primera implementación que omitió esta comprobación en 1962. ^{[8] [9]}

1. Establecer en y en . ${\displaystyle L}$ ${\displaystyle 0}$ ${\displaystyle R}$ ${\displaystyle n-1}$
2. Mientras , ${\displaystyle L\neq R}$
   1. Establezca (la posición del elemento central) en el techo de , que es el menor entero mayor o igual a . ${\displaystyle m}$ ${\displaystyle {\frac {L+R}{2}}}$ ${\displaystyle {\frac {L+R}{2}}}$
   2. Si , establezca en . ${\displaystyle A_{m}>T}$ ${\displaystyle R}$ ${\displaystyle m-1}$
   3. De lo contrario, ; establecido en . ${\displaystyle A_{m}\leq T}$ ${\displaystyle L}$ ${\displaystyle m}$
3. Ahora , la búsqueda está hecha. Si es así , devuelve . De lo contrario, la búsqueda finaliza por no tener éxito. ${\displaystyle L=R}$ ${\displaystyle A_{L}=T}$ ${\displaystyle L}$

¿Dónde ceilestá la función de techo? El pseudocódigo para esta versión es:

La función binary_search_alternative(A, n, T) es L := 0 R := n − 1 mientras L != R haga m := techo((L + R) / 2) si A[m] > T entonces R := m − 1 demás : L := m Si A[L] = T entonces  devuelve L devuelve un error

Elementos duplicados

El procedimiento puede devolver cualquier índice cuyo elemento sea igual al valor de destino, incluso si hay elementos duplicados en la matriz. Por ejemplo, si la matriz que se va a buscar era y el destino era , entonces sería correcto que el algoritmo devolviera el cuarto elemento (índice 3) o el quinto (índice 4). El procedimiento normal devolvería el cuarto elemento (índice 3) en este caso. No siempre devuelve el primer duplicado (considere cuál sigue devolviendo el cuarto elemento). Sin embargo, a veces es necesario encontrar el elemento más a la izquierda o el elemento más a la derecha para un valor de destino que está duplicado en la matriz. En el ejemplo anterior, el cuarto elemento es el elemento más a la izquierda del valor 4, mientras que el quinto elemento es el elemento más a la derecha del valor 4. El procedimiento alternativo anterior siempre devolverá el índice del elemento más a la derecha si existe dicho elemento. ^[9] ${\displaystyle [1,2,3,4,4,5,6,7]}$ ${\displaystyle 4}$ ${\displaystyle [1,2,4,4,4,5,6,7]}$

Procedimiento para encontrar el elemento más a la izquierda

Para encontrar el elemento más a la izquierda, se puede utilizar el siguiente procedimiento: ^[10]

1. Establecer en y en . ${\displaystyle L}$ ${\displaystyle 0}$ ${\displaystyle R}$ ${\displaystyle n}$
2. Mientras , ${\displaystyle L<R}$
   1. Establezca (la posición del elemento del medio) en el piso de , que es el mayor entero menor o igual a . ${\displaystyle m}$ ${\displaystyle {\frac {L+R}{2}}}$ ${\displaystyle {\frac {L+R}{2}}}$
   2. Si , establezca en . ${\displaystyle A_{m}<T}$ ${\displaystyle L}$ ${\displaystyle m+1}$
   3. De lo contrario, ; establecido en . ${\displaystyle A_{m}\geq T}$ ${\displaystyle R}$ ${\displaystyle m}$
3. Devolver . ${\displaystyle L}$

Si y , entonces es el elemento más a la izquierda que es igual a . Incluso si no está en la matriz, es el rango de en la matriz, o la cantidad de elementos en la matriz que son menores que . ${\displaystyle L<n}$ ${\displaystyle A_{L}=T}$ ${\displaystyle A_{L}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle L}$ ${\displaystyle T}$ ${\displaystyle T}$

¿Dónde floorestá la función de piso?, el pseudocódigo para esta versión es:

función binary_search_leftmost(A, n, T): L := 0 R := n mientras L < R: m := piso((L + R) / 2) si A[m] < T: L := m + 1 demás : R := m volver L

Procedimiento para encontrar el elemento más a la derecha

Para encontrar el elemento más a la derecha, se puede utilizar el siguiente procedimiento: ^[10]

1. Establecer en y en . ${\displaystyle L}$ ${\displaystyle 0}$ ${\displaystyle R}$ ${\displaystyle n}$
2. Mientras , ${\displaystyle L<R}$
   1. Establezca (la posición del elemento del medio) en el piso de , que es el mayor entero menor o igual a . ${\displaystyle m}$ ${\displaystyle {\frac {L+R}{2}}}$ ${\displaystyle {\frac {L+R}{2}}}$
   2. Si , establezca en . ${\displaystyle A_{m}>T}$ ${\displaystyle R}$ ${\displaystyle m}$
   3. De lo contrario, ; establecido en . ${\displaystyle A_{m}\leq T}$ ${\displaystyle L}$ ${\displaystyle m+1}$
3. Devolver . ${\displaystyle R-1}$

Si y , entonces es el elemento más a la derecha que es igual a . Incluso si no está en la matriz, es la cantidad de elementos en la matriz que son mayores que . ${\displaystyle R>0}$ ${\displaystyle A_{R-1}=T}$ ${\displaystyle A_{R-1}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle n-R}$ ${\displaystyle T}$

¿Dónde floorestá la función de piso?, el pseudocódigo para esta versión es:

función binary_search_rightmost(A, n, T): L := 0 R := n mientras L < R: m := piso((L + R) / 2) si A[m] > T: R := m demás : L := m + 1 devolver R - 1

Coincidencias aproximadas

La búsqueda binaria se puede adaptar para calcular coincidencias aproximadas. En el ejemplo anterior, se muestran el rango, el predecesor, el sucesor y el vecino más cercano para el valor de destino , que no está en la matriz. ${\displaystyle 5}$

El procedimiento anterior solo realiza coincidencias exactas , encontrando la posición de un valor objetivo. Sin embargo, es trivial extender la búsqueda binaria para realizar coincidencias aproximadas porque la búsqueda binaria opera en matrices ordenadas. Por ejemplo, la búsqueda binaria se puede utilizar para calcular, para un valor dado, su rango (el número de elementos más pequeños), predecesor (próximo elemento más pequeño), sucesor (próximo elemento más grande) y vecino más cercano . Las consultas de rango que buscan el número de elementos entre dos valores se pueden realizar con dos consultas de rango. ^[11]

• Las consultas de rango se pueden realizar con el procedimiento para encontrar el elemento más a la izquierda. El procedimiento devuelve la cantidad de elementos menores que el valor objetivo. ^[11]
• Las consultas de predecesores se pueden realizar con consultas de rango. Si el rango del valor de destino es , su predecesor es  . ^[12] ${\displaystyle r}$ ${\displaystyle r-1}$
• Para las consultas sucesoras, se puede utilizar el procedimiento para encontrar el elemento situado más a la derecha. Si el resultado de ejecutar el procedimiento para el valor de destino es , entonces el sucesor del valor de destino es  . ^[12] ${\displaystyle r}$ ${\displaystyle r+1}$
• El vecino más cercano del valor objetivo es su predecesor o sucesor, el que esté más cerca.
• Las consultas de rangos también son sencillas. ^[12] Una vez que se conocen los rangos de los dos valores, la cantidad de elementos mayores o iguales que el primer valor y menores que el segundo es la diferencia de los dos rangos. Este recuento se puede ajustar hacia arriba o hacia abajo en uno según si los puntos finales del rango se deben considerar como parte del rango y si la matriz contiene entradas que coinciden con esos puntos finales. ^[13]

Actuación

Un árbol que representa una búsqueda binaria. La matriz que se busca aquí es y el valor de destino es . ${\displaystyle [20,30,40,50,80,90,100]}$ ${\displaystyle 40}$

El peor caso se alcanza cuando la búsqueda llega al nivel más profundo del árbol, mientras que el mejor caso se alcanza cuando el valor objetivo es el elemento medio.

En términos del número de comparaciones, el rendimiento de la búsqueda binaria se puede analizar al ver la ejecución del procedimiento en un árbol binario. El nodo raíz del árbol es el elemento central de la matriz. El elemento central de la mitad inferior es el nodo hijo izquierdo de la raíz, y el elemento central de la mitad superior es el nodo hijo derecho de la raíz. El resto del árbol se construye de manera similar. A partir del nodo raíz, se recorren los subárboles izquierdo o derecho dependiendo de si el valor objetivo es menor o mayor que el nodo en consideración. ^{[6] [14]}

En el peor de los casos, la búsqueda binaria realiza iteraciones del bucle de comparación, donde la notación denota la función base que produce el mayor entero menor o igual que el argumento, y es el logaritmo binario . Esto se debe a que el peor de los casos se alcanza cuando la búsqueda alcanza el nivel más profundo del árbol, y siempre hay niveles en el árbol para cualquier búsqueda binaria. ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ${\textstyle \lfloor \cdot \rfloor }$ ${\textstyle \log _{2}}$ ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$

El peor caso también puede darse cuando el elemento de destino no está en la matriz. Si es uno menos que una potencia de dos, entonces este es siempre el caso. De lo contrario, la búsqueda puede realizar iteraciones si la búsqueda alcanza el nivel más profundo del árbol. Sin embargo, puede realizar iteraciones, que es uno menos que el peor caso, si la búsqueda termina en el segundo nivel más profundo del árbol. ^[15] ${\textstyle n}$ ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ${\textstyle \lfloor \log _{2}(n)\rfloor }$

En promedio, suponiendo que cada elemento tiene la misma probabilidad de ser buscado, la búsqueda binaria realiza iteraciones cuando el elemento de destino está en la matriz. Esto es aproximadamente igual a iteraciones. Cuando el elemento de destino no está en la matriz, la búsqueda binaria realiza iteraciones en promedio, suponiendo que el rango entre los elementos y los elementos externos tiene la misma probabilidad de ser buscado. ^[14] ${\displaystyle \lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n}$ ${\displaystyle \log _{2}(n)-1}$ ${\displaystyle \lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)}$

En el mejor caso, cuando el valor objetivo es el elemento central de la matriz, su posición se devuelve después de una iteración. ^[16]

En términos de iteraciones, ningún algoritmo de búsqueda que funcione únicamente comparando elementos puede exhibir un mejor desempeño promedio y en el peor de los casos que la búsqueda binaria. El árbol de comparación que representa la búsqueda binaria tiene la menor cantidad de niveles posible, ya que cada nivel por encima del nivel más bajo del árbol se llena por completo. ^[b] De lo contrario, el algoritmo de búsqueda puede eliminar algunos elementos en una iteración, lo que aumenta el número de iteraciones requeridas en el promedio y el peor de los casos. Este es el caso de otros algoritmos de búsqueda basados ​​en comparaciones, ya que si bien pueden funcionar más rápido en algunos valores objetivo, el desempeño promedio sobre todos los elementos es peor que la búsqueda binaria. Al dividir la matriz a la mitad, la búsqueda binaria garantiza que el tamaño de ambas submatrices sea lo más similar posible. ^[14]

Complejidad espacial

La búsqueda binaria requiere tres punteros a elementos, que pueden ser índices de matriz o punteros a ubicaciones de memoria, independientemente del tamaño de la matriz. Por lo tanto, la complejidad espacial de la búsqueda binaria se encuentra en el modelo de cálculo de Word-RAM . ${\displaystyle O(1)}$

Derivación del caso promedio

El número promedio de iteraciones realizadas por una búsqueda binaria depende de la probabilidad de que se busque cada elemento. El caso promedio es diferente para búsquedas exitosas y búsquedas fallidas. Se asumirá que cada elemento tiene la misma probabilidad de ser buscado para búsquedas exitosas. Para búsquedas fallidas, se asumirá que los intervalos entre y elementos externos tienen la misma probabilidad de ser buscados. El caso promedio para búsquedas exitosas es el número de iteraciones requeridas para buscar cada elemento exactamente una vez, dividido por , el número de elementos. El caso promedio para búsquedas fallidas es el número de iteraciones requeridas para buscar un elemento dentro de cada intervalo exactamente una vez, dividido por los intervalos. ^[14] ${\displaystyle n}$ ${\displaystyle n+1}$

Búsquedas exitosas

En la representación del árbol binario, una búsqueda exitosa puede representarse mediante una ruta desde la raíz hasta el nodo de destino, llamada ruta interna . La longitud de una ruta es el número de aristas (conexiones entre nodos) por las que pasa la ruta. El número de iteraciones realizadas por una búsqueda, dado que la ruta correspondiente tiene una longitud , es contando la iteración inicial. La longitud de la ruta interna es la suma de las longitudes de todas las rutas internas únicas. Dado que solo hay una ruta desde la raíz hasta cualquier nodo individual, cada ruta interna representa una búsqueda de un elemento específico. Si hay elementos, que es un entero positivo, y la longitud de la ruta interna es , entonces el número promedio de iteraciones para una búsqueda exitosa es , con la iteración única agregada para contar la iteración inicial. ^[14] ${\displaystyle l}$ ${\displaystyle l+1}$ ${\displaystyle n}$ ${\displaystyle I(n)}$ ${\displaystyle T(n)=1+{\frac {I(n)}{n}}}$

Dado que la búsqueda binaria es el algoritmo óptimo para buscar con comparaciones, este problema se reduce a calcular la longitud mínima de la ruta interna de todos los árboles binarios con nodos, que es igual a: ^[17] ${\displaystyle n}$

${\displaystyle I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor }$

Por ejemplo, en una matriz de 7 elementos, la raíz requiere una iteración, los dos elementos que se encuentran debajo de la raíz requieren dos iteraciones y los cuatro elementos que se encuentran debajo requieren tres iteraciones. En este caso, la longitud de la ruta interna es: ^[17]

${\displaystyle \sum _{k=1}^{7}\left\lfloor \log _{2}(k)\right\rfloor =0+2(1)+4(2)=2+8=10}$

El número promedio de iteraciones se basaría en la ecuación del caso promedio. La suma para se puede simplificar a: ^[14] ${\displaystyle 1+{\frac {10}{7}}=2{\frac {3}{7}}}$ ${\displaystyle I(n)}$

${\displaystyle I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor =(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}$

Sustituyendo la ecuación para en la ecuación para : ^[14] ${\displaystyle I(n)}$ ${\displaystyle T(n)}$

${\displaystyle T(n)=1+{\frac {(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2}{n}}=\lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n}$

Para un número entero , esto es equivalente a la ecuación para el caso promedio de una búsqueda exitosa especificada anteriormente. ${\displaystyle n}$

Búsquedas fallidas

Las búsquedas fallidas se pueden representar aumentando el árbol con nodos externos , lo que forma un árbol binario extendido . Si un nodo interno, o un nodo presente en el árbol, tiene menos de dos nodos secundarios, se agregan nodos secundarios adicionales, llamados nodos externos, de modo que cada nodo interno tenga dos secundarios. Al hacerlo, una búsqueda fallida se puede representar como una ruta a un nodo externo, cuyo padre es el único elemento que permanece durante la última iteración. Una ruta externa es una ruta desde la raíz a un nodo externo. La longitud de la ruta externa es la suma de las longitudes de todas las rutas externas únicas. Si hay elementos, que es un entero positivo, y la longitud de la ruta externa es , entonces el número promedio de iteraciones para una búsqueda fallida , con la iteración agregada para contar la iteración inicial. La longitud de la ruta externa se divide por en lugar de porque hay rutas externas, que representan los intervalos entre y fuera de los elementos de la matriz. ^[14] ${\displaystyle n}$ ${\displaystyle E(n)}$ ${\displaystyle T'(n)={\frac {E(n)}{n+1}}}$ ${\displaystyle n+1}$ ${\displaystyle n}$ ${\displaystyle n+1}$

Este problema se puede reducir de manera similar a determinar la longitud mínima del camino externo de todos los árboles binarios con nodos. Para todos los árboles binarios, la longitud del camino externo es igual a la longitud del camino interno más . ^[17] Sustituyendo la ecuación por : ^[14] ${\displaystyle n}$ ${\displaystyle 2n}$ ${\displaystyle I(n)}$

${\displaystyle E(n)=I(n)+2n=\left[(n+1)\left\lfloor \log _{2}(n+1)\right\rfloor -2^{\left\lfloor \log _{2}(n+1)\right\rfloor +1}+2\right]+2n=(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}}$

Sustituyendo la ecuación para en la ecuación para , se puede determinar el caso promedio de búsquedas fallidas: ^[14] ${\displaystyle E(n)}$ ${\displaystyle T'(n)}$

${\displaystyle T'(n)={\frac {(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}}{(n+1)}}=\lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)}$

Realización de procedimiento alternativo

Cada iteración del procedimiento de búsqueda binaria definido anteriormente realiza una o dos comparaciones, verificando si el elemento del medio es igual al objetivo en cada iteración. Suponiendo que cada elemento tiene la misma probabilidad de ser buscado, cada iteración realiza 1,5 comparaciones en promedio. Una variación del algoritmo verifica si el elemento del medio es igual al objetivo al final de la búsqueda. En promedio, esto elimina la mitad de una comparación de cada iteración. Esto reduce ligeramente el tiempo que toma cada iteración en la mayoría de las computadoras. Sin embargo, garantiza que la búsqueda tome el número máximo de iteraciones, agregando en promedio una iteración a la búsqueda. Debido a que el bucle de comparación se realiza solo veces en el peor de los casos, el ligero aumento en la eficiencia por iteración no compensa la iteración adicional para todos, excepto para valores muy grandes . ^{[c] [18] [19]} ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ ${\textstyle n}$

Tiempo de ejecución y uso de caché

Al analizar el rendimiento de la búsqueda binaria, otra consideración es el tiempo necesario para comparar dos elementos. Para números enteros y cadenas, el tiempo necesario aumenta linealmente a medida que aumenta la longitud de codificación (normalmente el número de bits ) de los elementos. Por ejemplo, comparar un par de números enteros sin signo de 64 bits requeriría comparar hasta el doble de bits que comparar un par de números enteros sin signo de 32 bits. El peor caso se da cuando los números enteros son iguales. Esto puede ser significativo cuando las longitudes de codificación de los elementos son grandes, como con tipos de números enteros grandes o cadenas largas, lo que hace que la comparación de elementos sea costosa. Además, comparar valores de punto flotante (la representación digital más común de números reales ) suele ser más costoso que comparar números enteros o cadenas cortas.

En la mayoría de las arquitecturas de ordenador, el procesador tiene una caché de hardware separada de la RAM . Dado que se encuentran dentro del propio procesador, las cachés son mucho más rápidas de acceder, pero suelen almacenar muchos menos datos que la RAM. Por tanto, la mayoría de los procesadores almacenan las ubicaciones de memoria a las que se ha accedido recientemente, junto con las ubicaciones de memoria cercanas a él. Por ejemplo, cuando se accede a un elemento de una matriz, el propio elemento puede almacenarse junto con los elementos que están almacenados cerca de él en la RAM, lo que hace que sea más rápido acceder secuencialmente a los elementos de la matriz que están cerca en índice entre sí ( localidad de referencia ). En una matriz ordenada, la búsqueda binaria puede saltar a ubicaciones de memoria distantes si la matriz es grande, a diferencia de los algoritmos (como la búsqueda lineal y el sondeo lineal en tablas hash ) que acceden a los elementos en secuencia. Esto aumenta ligeramente el tiempo de ejecución de la búsqueda binaria para matrices grandes en la mayoría de los sistemas. ^[20]

Búsqueda binaria versus otros esquemas

Las matrices ordenadas con búsqueda binaria son una solución muy ineficiente cuando las operaciones de inserción y eliminación se intercalan con la recuperación, y cada una de ellas requiere tiempo. Además, las matrices ordenadas pueden complicar el uso de la memoria, especialmente cuando se insertan elementos con frecuencia en la matriz. ^[21] Existen otras estructuras de datos que admiten una inserción y eliminación mucho más eficiente. La búsqueda binaria se puede utilizar para realizar una coincidencia exacta y la pertenencia a conjuntos (determinar si un valor de destino está en una colección de valores). Existen estructuras de datos que admiten una coincidencia exacta y una pertenencia a conjuntos más rápidas. Sin embargo, a diferencia de muchos otros esquemas de búsqueda, la búsqueda binaria se puede utilizar para una coincidencia aproximada eficiente, y normalmente se realizan dichas coincidencias a tiempo independientemente del tipo o la estructura de los propios valores. ^[22] Además, existen algunas operaciones, como encontrar el elemento más pequeño y el más grande, que se pueden realizar de manera eficiente en una matriz ordenada. ^[11] ${\textstyle O(n)}$ ${\textstyle O(\log n)}$

Búsqueda lineal

La búsqueda lineal es un algoritmo de búsqueda simple que revisa cada registro hasta encontrar el valor objetivo. La búsqueda lineal se puede realizar en una lista enlazada, lo que permite una inserción y eliminación más rápida que una matriz. La búsqueda binaria es más rápida que la búsqueda lineal para matrices ordenadas, excepto si la matriz es corta, aunque la matriz debe ordenarse de antemano. ^{[d] [24]} Todos los algoritmos de ordenación basados ​​en la comparación de elementos, como quicksort y merge sort , requieren al menos comparaciones en el peor de los casos. ^[25] A diferencia de la búsqueda lineal, la búsqueda binaria se puede utilizar para una coincidencia aproximada eficiente. Hay operaciones como encontrar el elemento más pequeño y más grande que se pueden realizar de manera eficiente en una matriz ordenada pero no en una matriz sin ordenar. ^[26] ${\textstyle O(n\log n)}$

Árboles

Los árboles de búsqueda binaria se buscan utilizando un algoritmo similar a la búsqueda binaria.

Un árbol binario de búsqueda es una estructura de datos de árbol binario que funciona según el principio de búsqueda binaria. Los registros del árbol están dispuestos en orden ordenado, y cada registro del árbol puede buscarse utilizando un algoritmo similar a la búsqueda binaria, que toma un tiempo logarítmico promedio. La inserción y eliminación también requieren un tiempo logarítmico promedio en árboles binarios de búsqueda. Esto puede ser más rápido que la inserción y eliminación en tiempo lineal de matrices ordenadas, y los árboles binarios conservan la capacidad de realizar todas las operaciones posibles en una matriz ordenada, incluidas las consultas de rango y aproximadas. ^{[22] [27]}

Sin embargo, la búsqueda binaria suele ser más eficiente para la búsqueda, ya que los árboles de búsqueda binaria probablemente estarán imperfectamente equilibrados, lo que dará como resultado un rendimiento ligeramente peor que la búsqueda binaria. Esto incluso se aplica a los árboles de búsqueda binaria equilibrados , árboles de búsqueda binaria que equilibran sus propios nodos, porque rara vez producen el árbol con la menor cantidad posible de niveles. A excepción de los árboles de búsqueda binaria equilibrados, el árbol puede estar severamente desequilibrado con pocos nodos internos con dos hijos, lo que da como resultado que el tiempo de búsqueda promedio y en el peor de los casos se acerque a las comparaciones. ^[e] Los árboles de búsqueda binaria ocupan más espacio que las matrices ordenadas. ^[29] ${\textstyle n}$

Los árboles binarios de búsqueda se prestan a la búsqueda rápida en la memoria externa almacenada en discos duros, ya que los árboles binarios de búsqueda se pueden estructurar de manera eficiente en sistemas de archivos. El árbol B generaliza este método de organización de árboles. Los árboles B se utilizan con frecuencia para organizar el almacenamiento a largo plazo, como bases de datos y sistemas de archivos . ^{[30] [31]}

Hash (hash)

Para implementar arreglos asociativos , las tablas hash , una estructura de datos que asigna claves a registros usando una función hash , son generalmente más rápidas que la búsqueda binaria en un arreglo ordenado de registros. ^[32] La mayoría de las implementaciones de tablas hash requieren solo tiempo constante amortizado en promedio. ^{[f] [34]} Sin embargo, el hash no es útil para coincidencias aproximadas, como calcular la clave siguiente más pequeña, siguiente más grande y más cercana, ya que la única información dada en una búsqueda fallida es que el objetivo no está presente en ningún registro. ^[35] La búsqueda binaria es ideal para tales coincidencias, realizándolas en tiempo logarítmico. La búsqueda binaria también admite coincidencias aproximadas. Algunas operaciones, como encontrar el elemento más pequeño y más grande, se pueden realizar de manera eficiente en arreglos ordenados pero no en tablas hash. ^[22]

Establecer algoritmos de membresía

Un problema relacionado con la búsqueda es la pertenencia a un conjunto . Cualquier algoritmo que realice búsquedas, como la búsqueda binaria, también se puede utilizar para la pertenencia a un conjunto. Hay otros algoritmos que son más adecuados específicamente para la pertenencia a un conjunto. Una matriz de bits es la más simple, útil cuando el rango de claves es limitado. Almacena de forma compacta una colección de bits , donde cada bit representa una clave única dentro del rango de claves. Las matrices de bits son muy rápidas y solo requieren tiempo. ^[36] El tipo Judy1 de matriz Judy maneja claves de 64 bits de manera eficiente. ^[37] ${\textstyle O(1)}$

Para obtener resultados aproximados, los filtros Bloom , otra estructura de datos probabilística basada en hash, almacenan un conjunto de claves mediante la codificación de las claves utilizando una matriz de bits y múltiples funciones hash. Los filtros Bloom son mucho más eficientes en cuanto al espacio que las matrices de bits en la mayoría de los casos y no mucho más lentos: con las funciones hash, las consultas de pertenencia solo requieren tiempo. Sin embargo, los filtros Bloom sufren de falsos positivos . ^{[g] [h] [39]} ${\textstyle k}$ ${\textstyle O(k)}$

Otras estructuras de datos

Existen estructuras de datos que pueden mejorar la búsqueda binaria en algunos casos, tanto para la búsqueda como para otras operaciones disponibles para matrices ordenadas. Por ejemplo, las búsquedas, las coincidencias aproximadas y las operaciones disponibles para matrices ordenadas se pueden realizar de manera más eficiente que la búsqueda binaria en estructuras de datos especializadas, como árboles de van Emde Boas , árboles de fusión , tries y matrices de bits . Estas estructuras de datos especializadas suelen ser más rápidas solo porque aprovechan las propiedades de las claves con un determinado atributo (normalmente claves que son números enteros pequeños) y, por tanto, consumirán tiempo o espacio para las claves que carecen de ese atributo. ^[22] Siempre que las claves se puedan ordenar, estas operaciones siempre se pueden realizar al menos de manera eficiente en una matriz ordenada independientemente de las claves. Algunas estructuras, como las matrices Judy, utilizan una combinación de enfoques para mitigar esto al tiempo que conservan la eficiencia y la capacidad de realizar coincidencias aproximadas. ^[37]

Variaciones

Búsqueda binaria uniforme

La búsqueda binaria uniforme almacena la diferencia entre el elemento actual y los dos siguientes elementos posibles en el medio en lugar de límites específicos.

La búsqueda binaria uniforme almacena, en lugar de los límites inferior y superior, la diferencia en el índice del elemento central desde la iteración actual hasta la siguiente iteración. De antemano se calcula una tabla de búsqueda que contiene las diferencias. Por ejemplo, si la matriz que se va a buscar es [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] , el elemento central ( ) sería 6 . En este caso, el elemento central de la submatriz izquierda ( [1, 2, 3, 4, 5] ) es 3 y el elemento central de la submatriz derecha ( [7, 8, 9, 10, 11] ) es 9 . La búsqueda binaria uniforme almacenaría el valor de 3 ya que ambos índices difieren de 6 en esta misma cantidad. ^[40] Para reducir el espacio de búsqueda, el algoritmo suma o resta este cambio del índice del elemento central. La búsqueda binaria uniforme puede ser más rápida en sistemas donde es ineficiente calcular el punto medio, como en las computadoras decimales . ^[41] ${\displaystyle m}$

Búsqueda exponencial

Visualización de la búsqueda exponencial que determina el límite superior para la búsqueda binaria posterior

La búsqueda exponencial extiende la búsqueda binaria a listas ilimitadas. Comienza por encontrar el primer elemento con un índice que sea a la vez una potencia de dos y mayor que el valor objetivo. Después, establece ese índice como el límite superior y cambia a la búsqueda binaria. Una búsqueda requiere iteraciones antes de que se inicie la búsqueda binaria y, como máximo, iteraciones de la búsqueda binaria, donde es la posición del valor objetivo. La búsqueda exponencial funciona en listas limitadas, pero se convierte en una mejora con respecto a la búsqueda binaria solo si el valor objetivo se encuentra cerca del comienzo de la matriz. ^[42] ${\textstyle \lfloor \log _{2}x+1\rfloor }$ ${\textstyle \lfloor \log _{2}x\rfloor }$ ${\textstyle x}$

Búsqueda por interpolación

Visualización de la búsqueda por interpolación mediante interpolación lineal. En este caso, no es necesaria la búsqueda porque la estimación de la ubicación del objetivo dentro de la matriz es correcta. Otras implementaciones pueden especificar otra función para estimar la ubicación del objetivo.

En lugar de calcular el punto medio, la búsqueda por interpolación estima la posición del valor objetivo, teniendo en cuenta los elementos más altos y más bajos de la matriz, así como la longitud de la matriz. Funciona sobre la base de que el punto medio no es la mejor estimación en muchos casos. Por ejemplo, si el valor objetivo está cerca del elemento más alto de la matriz, es probable que se encuentre cerca del final de la matriz. ^[43]

Una función de interpolación común es la interpolación lineal . Si es la matriz, son los límites inferior y superior respectivamente, y es el objetivo, entonces se estima que el objetivo está aproximadamente entre y . Cuando se utiliza la interpolación lineal, y la distribución de los elementos de la matriz es uniforme o casi uniforme, la búsqueda por interpolación realiza comparaciones. ^{[43] [44] [45]} ${\displaystyle A}$ ${\displaystyle L,R}$ ${\displaystyle T}$ ${\displaystyle (T-A_{L})/(A_{R}-A_{L})}$ ${\displaystyle L}$ ${\displaystyle R}$ ${\textstyle O(\log \log n)}$

En la práctica, la búsqueda por interpolación es más lenta que la búsqueda binaria para matrices pequeñas, ya que la búsqueda por interpolación requiere cálculos adicionales. Su complejidad temporal crece más lentamente que la búsqueda binaria, pero esto solo compensa los cálculos adicionales para matrices grandes. ^[43]

Cascada fraccional

En la cascada fraccionaria , cada matriz tiene punteros a cada segundo elemento de otra matriz, por lo que solo se debe realizar una búsqueda binaria para buscar en todas las matrices.

La cascada fraccionaria es una técnica que acelera las búsquedas binarias del mismo elemento en múltiples matrices ordenadas. La búsqueda en cada matriz por separado requiere tiempo, donde es el número de matrices. La cascada fraccionaria reduce esto a almacenando información específica en cada matriz sobre cada elemento y su posición en las otras matrices. ^{[46] [47]} ${\textstyle O(k\log n)}$ ${\textstyle k}$ ${\textstyle O(k+\log n)}$

El método de cascada fraccionaria se desarrolló originalmente para resolver de manera eficiente diversos problemas de geometría computacional . El método de cascada fraccionaria se ha aplicado en otros ámbitos, como la minería de datos y el enrutamiento del protocolo de Internet . ^[46]

Generalización a gráficos

La búsqueda binaria se ha generalizado para funcionar en ciertos tipos de gráficos, donde el valor objetivo se almacena en un vértice en lugar de un elemento de matriz. Los árboles de búsqueda binaria son una de esas generalizaciones: cuando se consulta un vértice (nodo) en el árbol, el algoritmo aprende que el vértice es el objetivo o, de lo contrario, en qué subárbol se ubicaría el objetivo. Sin embargo, esto se puede generalizar aún más de la siguiente manera: dado un gráfico no dirigido, ponderado positivamente y un vértice objetivo, el algoritmo aprende al consultar un vértice que es igual al objetivo, o se le da un borde incidente que está en la ruta más corta desde el vértice consultado hasta el objetivo. El algoritmo de búsqueda binaria estándar es simplemente el caso en el que el gráfico es una ruta. De manera similar, los árboles de búsqueda binaria son el caso en el que se dan los bordes de los subárboles izquierdo o derecho cuando el vértice consultado no es igual al objetivo. Para todos los gráficos no dirigidos, ponderados positivamente, existe un algoritmo que encuentra el vértice objetivo en las consultas en el peor de los casos. ^[48] ${\displaystyle O(\log n)}$

Búsqueda binaria ruidosa

En la búsqueda binaria ruidosa, existe una cierta probabilidad de que una comparación sea incorrecta.

Los algoritmos de búsqueda binaria ruidosa resuelven el caso en el que el algoritmo no puede comparar de manera confiable los elementos de la matriz. Para cada par de elementos, existe una cierta probabilidad de que el algoritmo haga la comparación incorrecta. La búsqueda binaria ruidosa puede encontrar la posición correcta del objetivo con una probabilidad dada que controla la confiabilidad de la posición obtenida. Cada procedimiento de búsqueda binaria ruidosa debe hacer al menos comparaciones en promedio, donde es la función de entropía binaria y es la probabilidad de que el procedimiento arroje la posición incorrecta. ^{[49] [50] [51]} El problema de la búsqueda binaria ruidosa puede considerarse como un caso del juego Rényi-Ulam , ^[52] una variante de Veinte preguntas donde las respuestas pueden ser incorrectas. ^[53] ${\displaystyle (1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}}$ ${\displaystyle H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)}$ ${\displaystyle \tau }$

Búsqueda binaria cuántica

Las computadoras clásicas están limitadas al peor caso de iteraciones exactas cuando realizan una búsqueda binaria. Los algoritmos cuánticos para la búsqueda binaria todavía están limitados a una proporción de consultas (que representan iteraciones del procedimiento clásico), pero el factor constante es menor que uno, lo que proporciona una complejidad temporal menor en las computadoras cuánticas . Cualquier procedimiento de búsqueda binaria cuántica exacta , es decir, un procedimiento que siempre produce el resultado correcto, requiere al menos consultas en el peor caso, donde es el logaritmo natural . ^[54] Hay un procedimiento de búsqueda binaria cuántica exacta que se ejecuta en consultas en el peor caso. ^[55] En comparación, el algoritmo de Grover es el algoritmo cuántico óptimo para buscar una lista desordenada de elementos, y requiere consultas. ^[56] ${\textstyle \lfloor \log _{2}n+1\rfloor }$ ${\textstyle \log _{2}n}$ ${\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n}$ ${\textstyle \ln }$ ${\textstyle 4\log _{605}n\approx 0.433\log _{2}n}$ ${\displaystyle O({\sqrt {n}})}$

Historia

La idea de ordenar una lista de elementos para permitir una búsqueda más rápida se remonta a la antigüedad. El ejemplo más antiguo conocido fue la tablilla Inakibit-Anu de Babilonia que data de alrededor del año  200 a . C. La tablilla contenía alrededor de 500 números sexagesimales y sus recíprocos ordenados en orden lexicográfico , lo que facilitaba la búsqueda de una entrada específica. Además, se descubrieron varias listas de nombres que se ordenaban por su primera letra en las islas del Egeo . Catholicon , un diccionario latino terminado en 1286 d. C., fue la primera obra que describió reglas para ordenar las palabras en orden alfabético, en lugar de solo las primeras letras. ^[9]

En 1946, John Mauchly hizo la primera mención de la búsqueda binaria como parte de las Moore School Lectures , un curso universitario seminal y fundacional en informática. ^[9] En 1957, William Wesley Peterson publicó el primer método para la búsqueda por interpolación. ^{[9] [57]} Cada algoritmo de búsqueda binaria publicado funcionó solo para matrices cuya longitud es uno menos que una potencia de dos ^[i] hasta 1960, cuando Derrick Henry Lehmer publicó un algoritmo de búsqueda binaria que funcionaba en todas las matrices. ^[59] En 1962, Hermann Bottenbruch presentó una implementación ALGOL 60 de la búsqueda binaria que colocó la comparación de igualdad al final, aumentando el número promedio de iteraciones en uno, pero reduciendo a uno el número de comparaciones por iteración. ^[8] La búsqueda binaria uniforme fue desarrollada por AK Chandra de la Universidad de Stanford en 1971. ^[9] En 1986, Bernard Chazelle y Leonidas J. Guibas introdujeron la cascada fraccionaria como un método para resolver numerosos problemas de búsqueda en geometría computacional . ^{[46] [60] [61]}

Problemas de implementación

Aunque la idea básica de la búsqueda binaria es comparativamente sencilla, los detalles pueden ser sorprendentemente complicados.

—Donald  Knuth ^[2]

Cuando Jon Bentley asignó la búsqueda binaria como un problema en un curso para programadores profesionales, descubrió que el noventa por ciento no lograba proporcionar una solución correcta después de varias horas de trabajo en él, principalmente porque las implementaciones incorrectas no se ejecutaban o devolvían una respuesta incorrecta en casos extremos poco frecuentes . ^[62] Un estudio publicado en 1988 muestra que el código preciso para ello solo se encuentra en cinco de veinte libros de texto. ^[63] Además, la propia implementación de la búsqueda binaria de Bentley, publicada en su libro de 1986 Programming Pearls , contenía un error de desbordamiento que permaneció sin detectar durante más de veinte años. La implementación de la búsqueda binaria de la biblioteca del lenguaje de programación Java tuvo el mismo error de desbordamiento durante más de nueve años. ^[64]

En una implementación práctica, las variables utilizadas para representar los índices a menudo serán de tamaño fijo (números enteros), y esto puede resultar en un desbordamiento aritmético para matrices muy grandes. Si el punto medio del intervalo se calcula como , entonces el valor de puede exceder el rango de números enteros del tipo de datos utilizado para almacenar el punto medio, incluso si y están dentro del rango. Si y son no negativos, esto se puede evitar calculando el punto medio como . ^[65] ${\displaystyle {\frac {L+R}{2}}}$ ${\displaystyle L+R}$ ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle L}$ ${\displaystyle R}$ ${\displaystyle L+{\frac {R-L}{2}}}$

Un bucle infinito puede ocurrir si las condiciones de salida del bucle no están definidas correctamente. Una vez que se excede , la búsqueda ha fallado y debe transmitir el fallo de la búsqueda. Además, se debe salir del bucle cuando se encuentra el elemento de destino, o en el caso de una implementación donde esta comprobación se traslada al final, se deben realizar comprobaciones para determinar si la búsqueda fue exitosa o falló al final. Bentley descubrió que la mayoría de los programadores que implementaron incorrectamente la búsqueda binaria cometieron un error al definir las condiciones de salida. ^{[8] [66]} ${\displaystyle L}$ ${\displaystyle R}$

Soporte de biblioteca

Las bibliotecas estándar de muchos lenguajes incluyen rutinas de búsqueda binaria:

• C proporciona la función bsearch() en su biblioteca estándar , que normalmente se implementa mediante búsqueda binaria, aunque el estándar oficial no lo requiere así. ^[67]
• La biblioteca estándar de C++ proporciona las funciones binary_search(), lower_bound(), upper_bound()y equal_range(). ^[68]
• La biblioteca estándar de Dstd.range , Phobos, en el módulo proporciona un tipo SortedRange(devuelto por las funciones sort()y assumeSorted()) con los métodos contains(), equaleRange(), lowerBound()y trisect(), que utilizan técnicas de búsqueda binaria de forma predeterminada para rangos que ofrecen acceso aleatorio. ^[69]
• COBOL proporciona el SEARCH ALLverbo para realizar búsquedas binarias en tablas ordenadas de COBOL. ^[70]
• El paquete de biblioteca estándar de Gosort contiene las funciones Search, SearchInts, SearchFloat64s, y SearchStrings, que implementan la búsqueda binaria general, así como implementaciones específicas para buscar porciones de números enteros, números de punto flotante y cadenas, respectivamente. ^[71]
• Java ofrece un conjunto de métodos estáticos sobrecargados en las clases y en el paquete estándar para realizar búsquedas binarias en matrices Java y en s, respectivamente. ^{[72] [73]}binarySearch()ArraysCollectionsjava.utilList
• El .NET Framework 2.0 de Microsoft ofrece versiones genéricas estáticas del algoritmo de búsqueda binaria en sus clases base de colección. Un ejemplo sería System.Arrayel método de BinarySearch<T>(T[] array, T value). ^[74]
• Para Objective-C , el marco CocoaNSArray -indexOfObject:inSortedRange:options:usingComparator: proporciona el método en Mac OS X 10.6+. ^{[75] El marco} Core Foundation C de Apple también contiene una CFArrayBSearchValues()función. ^[76]
• Python proporciona el bisectmódulo que mantiene una lista en orden ordenado sin tener que ordenar la lista después de cada inserción. ^[77]
• La clase Array de Rubybsearch incluye un método con coincidencia aproximada incorporada. ^[78]
• La primitiva de corte de Rustbinary_search() proporciona , binary_search_by(), binary_search_by_key(), y partition_point(). ^[79]

Véase también

• Método de bisección  : algoritmo para encontrar un cero de una función; la misma idea se utiliza para resolver ecuaciones en números reales.
• Búsqueda binaria multiplicativa  : variación de la búsqueda binaria con cálculo simplificado del punto medio

Notas y referencias

Este artículo fue enviado a WikiJournal of Science para su revisión académica externa por pares en 2018 (informes de los revisores). El contenido actualizado fue reintegrado a la página de Wikipedia bajo una licencia CC-BY-SA-3.0 ( 2019 ). La versión de registro revisada es: Anthony Lin; et al. (2 de julio de 2019). "Algoritmo de búsqueda binaria" (PDF) . WikiJournal of Science . 2 (1): 5. doi : 10.15347/WJS/2019.005 . ISSN  2470-6345. Wikidata  Q81434400.

Notas

1. La notación Big O es , y es el logaritmo . En la notación Big O, la base del logaritmo no importa ya que cada logaritmo de una base dada es un factor constante de otro logaritmo de otra base. Es decir, , donde es una constante. ${\displaystyle O}$ ${\displaystyle \log }$ ${\displaystyle \log _{b}(n)=\log _{k}(n)\div \log _{k}(b)}$ ${\displaystyle \log _{k}(b)}$
2. Cualquier algoritmo de búsqueda basado únicamente en comparaciones se puede representar mediante un árbol de comparación binario. Una ruta interna es cualquier ruta desde la raíz hasta un nodo existente. Sea la longitud de la ruta interna , la suma de las longitudes de todas las rutas internas. Si cada elemento tiene la misma probabilidad de ser buscado, el caso promedio es o simplemente uno más el promedio de todas las longitudes de las rutas internas del árbol. Esto se debe a que las rutas internas representan los elementos que el algoritmo de búsqueda compara con el objetivo. Las longitudes de estas rutas internas representan el número de iteraciones después del nodo raíz. Sumar el promedio de estas longitudes a la iteración en la raíz produce el caso promedio. Por lo tanto, para minimizar el número promedio de comparaciones, se debe minimizar la longitud de la ruta interna. Resulta que el árbol para la búsqueda binaria minimiza la longitud de la ruta interna. Knuth 1998 demostró que la longitud de la ruta externa (la longitud de la ruta sobre todos los nodos donde ambos hijos están presentes para cada nodo ya existente) se minimiza cuando los nodos externos (los nodos sin hijos) se encuentran dentro de dos niveles consecutivos del árbol. Esto también se aplica a las rutas internas, ya que la longitud de la ruta interna está relacionada linealmente con la longitud de la ruta externa . Para cualquier árbol de nodos, . Cuando cada subárbol tiene un número similar de nodos, o equivalentemente la matriz se divide en mitades en cada iteración, los nodos externos, así como sus nodos padre interiores, se encuentran dentro de dos niveles. De ello se deduce que la búsqueda binaria minimiza el número de comparaciones promedio, ya que su árbol de comparación tiene la longitud de ruta interna más baja posible. ^[14] ${\displaystyle I}$ ${\displaystyle 1+{\frac {I}{n}}}$ ${\displaystyle I}$ ${\displaystyle I}$ ${\displaystyle E}$ ${\displaystyle n}$ ${\displaystyle I=E-2n}$
3. Knuth 1998 demostró en su modelo de computadora MIX , que Knuth diseñó como una representación de una computadora común, que el tiempo promedio de ejecución de esta variación para una búsqueda exitosa es de unidades de tiempo en comparación con las unidades para una búsqueda binaria regular. La complejidad temporal para esta variación crece ligeramente más lentamente, pero a costa de una mayor complejidad inicial. ^[18] ${\textstyle 17.5\log _{2}n+17}$ ${\textstyle 18\log _{2}n-16}$
4. Knuth 1998 realizó un análisis formal del rendimiento temporal de ambos algoritmos de búsqueda. En la computadora MIX de Knuth, que Knuth diseñó como una representación de una computadora común, la búsqueda binaria toma en promedio unidades de tiempo para una búsqueda exitosa, mientras que la búsqueda lineal con un nodo centinela al final de la lista toma unidades. La búsqueda lineal tiene una complejidad inicial menor porque requiere un cálculo mínimo, pero rápidamente supera a la búsqueda binaria en complejidad. En la computadora MIX, la búsqueda binaria solo supera a la búsqueda lineal con un nodo centinela si . ^{[14] [23]} ${\textstyle 18\log n-16}$ ${\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}$ ${\textstyle n>44}$
5. Insertar los valores en orden ordenado o en un patrón de clave alternado de menor a mayor dará como resultado un árbol de búsqueda binario que maximiza el tiempo de búsqueda promedio y en el peor de los casos. ^[28]
6. Es posible buscar algunas implementaciones de tablas hash en un tiempo constante garantizado. ^[33]
7. Esto se debe a que simplemente configurar todos los bits a los que apuntan las funciones hash para una clave específica puede afectar las consultas de otras claves que tienen una ubicación hash común para una o más de las funciones. ^[38]
8. Existen mejoras del filtro Bloom que mejoran su complejidad o admiten la eliminación; por ejemplo, el filtro cuckoo explota el hash cuckoo para obtener estas ventajas. ^[38]
9. Es decir, matrices de longitud 1, 3, 7, 15, 31... ^[58]

Citas

1. Williams, Jr., Louis F. (22 de abril de 1976). Una modificación del método de búsqueda de medio intervalo (búsqueda binaria). Actas de la 14.ª Conferencia del Sudeste de la ACM. ACM. págs. 95–101. doi : 10.1145/503561.503582 . Archivado desde el original el 12 de marzo de 2017. Consultado el 29 de junio de 2018 .
2. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Búsqueda binaria".
3. Butterfield y Ngondi 2016, pág. 46.
4. Cormen y otros. 2009, pág. 39.
5. Weisstein, Eric W. "Búsqueda binaria". MathWorld .
6. Flores, Ivan; Madpis, George (1 de septiembre de 1971). "Longitud de búsqueda binaria promedio para listas densas ordenadas". Comunicaciones de la ACM . 14 (9): 602–603. doi : 10.1145/362663.362752 . ISSN  0001-0782. S2CID  43325465.
7. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Algoritmo B".
8. Bottenbruch, Hermann (1 de abril de 1962). "Estructura y uso de ALGOL 60". Revista de la ACM . 9 (2): 161–221. doi : 10.1145/321119.321120 . ISSN  0004-5411. S2CID  13406983.El procedimiento se describe en la página 214 (§43), titulada "Programa para búsqueda binaria".
9. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Historia y bibliografía".
10. Kasahara y Morishita 2006, págs. 8–9.
11. Sedgewick & Wayne 2011, §3.1, subsección "Rango y selección".
12. Goldman & Goldman 2008, págs. 461–463.
13. Sedgewick & Wayne 2011, §3.1, subsección "Consultas de rango".
14. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Análisis adicional de la búsqueda binaria".
15. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada"), "Teorema B".
16. Chang 2003, pág. 169.
17. Knuth 1997, §2.3.4.5 ("Longitud de la ruta").
18. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Ejercicio 23".
19. Rolfe, Timothy J. (1997). "Derivación analítica de comparaciones en búsqueda binaria". Boletín ACM SIGNUM . 32 (4): 15–19. doi : 10.1145/289251.289255 . S2CID  23752485.
20. Khuong, Paul-Virak; Morin, Pat (2017). "Diseños de matrices para búsquedas basadas en comparaciones". Journal of Experimental Algorithmics . 22 . Artículo 1.3. arXiv : 1509.05053 . doi :10.1145/3053370. S2CID  23752485.
21. Knuth 1997, §2.2.2 ("Asignación secuencial").
22. Beame, Paul; Fich, Faith E. (2001). "Límites óptimos para el problema del predecesor y problemas relacionados". Revista de Ciencias de la Computación y de Sistemas . 65 (1): 38–72. doi : 10.1006/jcss.2002.1822 .
23. Knuth 1998, Respuestas a los ejercicios (§6.2.1) para el "Ejercicio 5".
24. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada").
25. Knuth 1998, §5.3.1 ("Ordenación por comparación mínima").
26. Sedgewick y Wayne 2011, §3.2 ("Tablas de símbolos ordenadas").
27. Sedgewick & Wayne 2011, §3.2 ("Árboles de búsqueda binaria"), subsección "Métodos basados ​​en orden y eliminación".
28. Knuth 1998, §6.2.2 ("Búsqueda de árboles binarios"), subsección "¿Pero qué pasa en el peor de los casos?".
29. Sedgewick & Wayne 2011, §3.5 ("Aplicaciones"), "¿Qué implementación de tabla de símbolos debería utilizar?".
30. Knuth 1998, §5.4.9 ("Discos y tambores").
31. Knuth 1998, §6.2.4 ("Árboles multidireccionales").
32. Knuth 1998, §6.4 ("Hash").
33. Knuth 1998, §6.4 ("Hashing"), subsección "Historial".
34. Dietzfelbinger, Martín; Karlín, Anna ; Mehlhorn, Kurt ; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (agosto de 1994). "Hash dinámico perfecto: límites superior e inferior". Revista SIAM de Computación . 23 (4): 738–761. doi :10.1137/S0097539791194094.
35. Morin, Pat. «Tablas hash» (PDF) . pág. 1. Archivado (PDF) del original el 9 de octubre de 2022. Consultado el 28 de marzo de 2016 .
36. Knuth 2011, §7.1.3 ("Trucos y técnicas bit a bit").
37. Silverstein, Alan, Manual de taller de Judy IV (PDF) , Hewlett-Packard , págs. 80–81, archivado (PDF) desde el original el 9 de octubre de 2022
38. Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Filtro Cuckoo: prácticamente mejor que Bloom . Actas de la 10.ª Conferencia Internacional de la ACM sobre Experimentos y Tecnologías Emergentes de Redes. págs. 75–88. doi : 10.1145/2674005.2674994 .
39. Bloom, Burton H. (1970). "Compensaciones espacio/tiempo en la codificación hash con errores permitidos". Comunicaciones de la ACM . 13 (7): 422–426. CiteSeerX 10.1.1.641.9096 . doi :10.1145/362686.362692. S2CID  7931252. 
40. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Una variación importante".
41. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Algoritmo U".
42. Moffat y Turpin 2002, pág. 33.
43. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Búsqueda por interpolación".
44. Knuth 1998, §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Ejercicio 22".
45. Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). "Búsqueda por interpolación: una búsqueda log log n". Comunicaciones de la ACM . 21 (7): 550–553. doi : 10.1145/359545.359557 . S2CID  11089655.
46. Chazelle, Bernard ; Liu, Ding (6 de julio de 2001). Límites inferiores para búsqueda de intersecciones y cascada fraccional en dimensiones superiores. 33.° Simposio ACM sobre teoría de la computación . ACM. págs. 322–329. doi :10.1145/380752.380818. ISBN 978-1-58113-349-3. Recuperado el 30 de junio de 2018 .
47. Chazelle, Bernard ; Liu, Ding (1 de marzo de 2004). "Límites inferiores para la búsqueda de intersecciones y la cascada fraccional en una dimensión superior" (PDF) . Journal of Computer and System Sciences . 68 (2): 269–284. CiteSeerX 10.1.1.298.7772 . doi :10.1016/j.jcss.2003.07.003. ISSN  0022-0000. Archivado (PDF) desde el original el 9 de octubre de 2022 . Consultado el 30 de junio de 2018 . 
48. Emamjomeh-Zadeh, Ehsan; Kempe, David; Singhal, Vikrant (2016). Búsqueda binaria determinista y probabilística en grafos . 48.º Simposio ACM sobre teoría de la computación . págs. 519–532. arXiv : 1503.00805 . doi :10.1145/2897518.2897656.
49. Ben-Or, Michael; Hassidim, Avinatan (2008). "El aprendiz bayesiano es óptimo para la búsqueda binaria ruidosa (y también bastante bueno para la cuántica)" (PDF) . 49.° Simposio sobre Fundamentos de la Ciencia de la Computación . pp. 221–230. doi :10.1109/FOCS.2008.58. ISBN. 978-0-7695-3436-7. Archivado (PDF) del original el 9 de octubre de 2022.
50. Pelc, Andrzej (1989). "Búsqueda con probabilidad de error conocida". Ciencias Informáticas Teóricas . 63 (2): 185–202. doi : 10.1016/0304-3975(89)90077-7 .
51. Rivest, Ronald L. ; Meyer, Albert R. ; Kleitman, Daniel J. ; Winklmann, K. Cómo afrontar errores en procedimientos de búsqueda binaria . 10º Simposio ACM sobre teoría de la computación . doi : 10.1145/800133.804351 .
52. Pelc, Andrzej (2002). "Búsqueda de juegos con errores: cincuenta años de lidiar con los mentirosos". Theoretical Computer Science . 270 (1–2): 71–109. doi : 10.1016/S0304-3975(01)00303-6 .
53. Rényi, Alfred (1961). "Sobre un problema de teoría de la información". Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei (en húngaro). 6 : 505–516. SEÑOR  0143666.
54. Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). "Complejidades cuánticas de búsqueda ordenada, ordenación y distinción de elementos". Algorithmica . 34 (4): 429–448. arXiv : quant-ph/0102078 . doi :10.1007/s00453-002-0976-3. S2CID  13717616.
55. Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). "Algoritmos cuánticos para el problema de búsqueda ordenada mediante programación semidefinida". Physical Review A . 75 (3). 032335. arXiv : quant-ph/0608161 . Código Bibliográfico :2007PhRvA..75c2335C. doi :10.1103/PhysRevA.75.032335. S2CID  41539957.
56. Grover, Lov K. (1996). Un algoritmo mecánico cuántico rápido para búsquedas en bases de datos . 28.º Simposio ACM sobre teoría de la computación . Filadelfia, PA. págs. 212–219. arXiv : quant-ph/9605043 . doi :10.1145/237814.237866.
57. Peterson, William Wesley (1957). "Direccionamiento para almacenamiento de acceso aleatorio". Revista IBM de investigación y desarrollo . 1 (2): 130–146. doi :10.1147/rd.12.0130.
58. "2 ⁿ −1". OEIS A000225 Archivado el 8 de junio de 2016 en Wayback Machine . Consultado el 7 de mayo de 2016.
59. Lehmer, Derrick (1960). "Enseñanza de trucos combinatorios a una computadora". Actas de simposios sobre matemáticas aplicadas . 10 : 180-181. doi : 10.1090/psapm/010 . ISBN. 9780821813102.
60. Chazelle, Bernard ; Guibas, Leonidas J. (1986). "Cascada fraccional: I. Una técnica de estructuración de datos" (PDF) . Algorithmica . 1 (1–4): 133–162. CiteSeerX 10.1.1.117.8349 . doi :10.1007/BF01840440. S2CID  12745042. 
61. Chazelle, Bernard ; Guibas, Leonidas J. (1986), "Cascada fraccional: II. Aplicaciones" (PDF) , Algorithmica , 1 (1–4): 163–191, doi :10.1007/BF01840441, S2CID  11232235
62. Bentley 2000, §4.1 ("El desafío de la búsqueda binaria").
63. Pattis, Richard E. (1988). "Errores en los libros de texto en la búsqueda binaria". Boletín SIGCSE . 20 : 190–194. doi :10.1145/52965.53012.
64. Bloch, Joshua (2 de junio de 2006). «Extra, extra – lea todo sobre esto: casi todas las búsquedas binarias y ordenaciones por combinación están rotas». Blog de investigación de Google . Archivado desde el original el 1 de abril de 2016. Consultado el 21 de abril de 2016 .
65. Ruggieri, Salvatore (2003). "Sobre el cálculo de la semisuma de dos números enteros" (PDF) . Information Processing Letters . 87 (2): 67–71. CiteSeerX 10.1.1.13.5631 . doi :10.1016/S0020-0190(03)00263-1. Archivado (PDF) desde el original el 3 de julio de 2006 . Consultado el 19 de marzo de 2016 . 
66. Bentley 2000, §4.4 ("Principios").
67. "bsearch – búsqueda binaria en una tabla ordenada". Especificaciones básicas de The Open Group (7.ª ed.). The Open Group . 2013. Archivado desde el original el 21 de marzo de 2016. Consultado el 28 de marzo de 2016 .
68. Stroustrup 2013, pág. 945.
69. "std.range - Lenguaje de programación D". dlang.org . Consultado el 29 de abril de 2020 .
70. Unisys (2012), Manual de referencia de programación COBOL ANSI-85 , vol. 1, págs. 598–601
71. "Ordenación de paquetes". El lenguaje de programación Go . Archivado desde el original el 25 de abril de 2016. Consultado el 28 de abril de 2016 .
72. "java.util.Arrays". Documentación de Java Platform Standard Edition 8 . Oracle Corporation . Archivado desde el original el 29 de abril de 2016 . Consultado el 1 de mayo de 2016 .
73. "java.util.Collections". Documentación de Java Platform Standard Edition 8 . Oracle Corporation . Archivado desde el original el 23 de abril de 2016 . Consultado el 1 de mayo de 2016 .
74. "Método List<T>.BinarySearch (T)". Microsoft Developer Network . Archivado desde el original el 7 de mayo de 2016. Consultado el 10 de abril de 2016 .
75. "NSArray". Biblioteca para desarrolladores de Mac . Apple Inc. Archivado desde el original el 17 de abril de 2016. Consultado el 1 de mayo de 2016 .
76. "CFArray". Biblioteca para desarrolladores de Mac . Apple Inc. Archivado desde el original el 20 de abril de 2016. Consultado el 1 de mayo de 2016 .
77. "8.6. bisect — Algoritmo de bisección de matrices". La biblioteca estándar de Python . Python Software Foundation. Archivado desde el original el 25 de marzo de 2018 . Consultado el 26 de marzo de 2018 .
78. Fitzgerald 2015, pág. 152.
79. "Primitive Type slice". Biblioteca estándar de Rust . Fundación Rust. 2024. Consultado el 25 de mayo de 2024 .

Fuentes

• Bentley, Jon (2000). Perlas de programación (2.ª ed.). Addison-Wesley . ISBN 978-0-201-65788-3.
• Butterfield, Andrew; Ngondi, Gerard E. (2016). Diccionario de informática (7.ª ed.). Oxford, Reino Unido: Oxford University Press . ISBN 978-0-19-968897-5.
• Chang, Shi-Kuo (2003). Estructuras de datos y algoritmos . Ingeniería de software e ingeniería del conocimiento. Vol. 13. Singapur: World Scientific . ISBN 978-981-238-348-8.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009). Introducción a los algoritmos (3ª ed.). MIT Press y McGraw-Hill. ISBN 978-0-262-03384-8.
• Fitzgerald, Michael (2015). Referencia de bolsillo Ruby . Sebastopol, California: O'Reilly Media . ISBN 978-1-4919-2601-7.
• Goldman, Sally A. ; Goldman, Kenneth J. (2008). Una guía práctica para estructuras de datos y algoritmos utilizando Java . Boca Raton, Florida: CRC Press . ISBN 978-1-58488-455-2.
• Kasahara, Masahiro; Morishita, Shinichi (2006). Procesamiento de secuencias genómicas a gran escala . Londres, Reino Unido: Imperial College Press. ISBN 978-1-86094-635-6.
• Knuth, Donald (1997). Algoritmos fundamentales . El arte de la programación informática . Vol. 1 (3.ª ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-89683-1.
• Knuth, Donald (1998). Ordenación y búsqueda . El arte de la programación informática . Vol. 3 (2.ª ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-89685-5.
• Knuth, Donald (2011). Algoritmos combinatorios . El arte de la programación informática . Vol. 4A (1.ª ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-03804-0.
• Moffat, Alistair; Turpin, Andrew (2002). Algoritmos de compresión y codificación . Hamburgo, Alemania: Kluwer Academic Publishers. doi :10.1007/978-1-4615-0935-6. ISBN 978-0-7923-7668-2.
• Sedgewick, Robert ; Wayne, Kevin (2011). Algoritmos (4.ª ed.). Upper Saddle River, Nueva Jersey: Addison-Wesley Professional. ISBN 978-0-321-57351-3.Versión web condensada; versión del libro.
• Stroustrup, Bjarne (2013). El lenguaje de programación C++ (4.ª ed.). Upper Saddle River, Nueva Jersey: Addison-Wesley Professional. ISBN 978-0-321-56384-2.

Enlaces externos

• Diccionario NIST de algoritmos y estructuras de datos: búsqueda binaria
• Comparaciones y evaluaciones comparativas de una variedad de implementaciones de búsqueda binaria en C Archivado el 25 de septiembre de 2019 en Wayback Machine