Búsqueda binaria

En informática , la búsqueda binaria , también conocida como búsqueda por intervalos de mitades , ^{[ 1 ]} búsqueda logarítmica , ^{[ 2 ]} o selección binaria , ^{[ 3 ]} es un algoritmo de búsqueda que encuentra la posición de un valor objetivo dentro de un arreglo ordenado . ^{[ 4 ]}^{[ 5 ]} La búsqueda binaria compara el valor objetivo con el elemento central del arreglo. 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 central para compararlo 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 el arreglo.

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

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 arreglos. Esta técnica resuelve eficientemente diversos 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 con arreglos ordenados. Comienza comparando un elemento en el medio del arreglo con el valor objetivo. Si el valor objetivo coincide con el elemento, se devuelve su posición en el arreglo. Si el valor objetivo es menor que el elemento, la búsqueda continúa en la mitad inferior del arreglo. Si el valor objetivo es mayor que el elemento, la búsqueda continúa en la mitad superior del arreglo. De esta manera, el algoritmo elimina en cada iteración la mitad en la que el valor objetivo no puede estar. ^{[ 7 ]}

Procedimiento

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

Colocar $L$ a $0$ y $R$ a $n-1$ .
Si $L>R$ La búsqueda finaliza sin éxito.
Colocar $m$ (la posición del elemento central) a $L$ más el piso de ${\frac {RL}{2}}$ , que es el mayor número entero menor o igual que ${\frac {RL}{2}}$ .
Si $A_{m}<T$ , colocar $L$ a $m+1$ y pasa al paso 2.
Si $A_{m}>T$ , colocar $R$ a $m-1$ y pasa al paso 2.
Ahora $A_{m}=T$ , la búsqueda ha finalizado; regresar $m$ .

Este procedimiento iterativo realiza un seguimiento de los límites de búsqueda con las dos variables. $L$ y $R$ El procedimiento puede expresarse en pseudocódigo de la siguiente manera, donde los nombres y tipos de las variables permanecen iguales que arriba, floores la función piso y unsuccessfulse refiere a un valor específico que indica el fallo de la búsqueda. ^{[ 7 ]}

La función binary_search(A, n, T) es L := 0 R := n − 1 mientras L ≤ R hacer m := L + piso((R - L) / 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; devolver unsuccessful.

Alternativamente, el algoritmo puede tomar el techo de ${\frac {RL}{2}}$ Esto puede cambiar el resultado si el valor objetivo aparece más de una vez en la matriz.

Procedimiento alternativo

En el procedimiento anterior, el algoritmo comprueba si el elemento central ( $m$ ) es igual al objetivo ( $T$ ) en cada iteración. Algunas implementaciones omiten esta verificación durante cada iteración. El algoritmo realizaría esta verificación solo cuando queda un elemento (cuando $L=R$ ). 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 requiere solo una iteración más en promedio. ^{[ 8 ]}

Hermann Bottenbruch publicó la primera implementación que omitía esta verificación en 1962. ^{[ 8 ]}^{[ 9 ]}

Colocar $L$ a $0$ y $R$ a $n-1$ .
Mientras $L\neq R$ $L\neq R$ ,
1. Colocar $m$ (la posición del elemento central) a $L$ más el techo de ${\frac {RL}{2}}$ , que es el menor número entero mayor o igual que ${\frac {RL}{2}}$ .
2. Si $A_{m}>T$ , colocar $R$ a $m-1$ .
3. Demás, $A_{m}\leq T$ ; colocar $L$ a $m$ .
Ahora $L=R$ , la búsqueda ha terminado. Si $A_{L}=T$ , devolver $L$ En caso contrario, la búsqueda finaliza sin éxito.

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

función binary_search_alternative(A, n, T) es L := 0 R := n − 1 mientras L != R hacer m := L + ceil((R - L) / 2) Si A[m] > T, entonces R := m − 1; de lo contrario : 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 objetivo, incluso si hay elementos duplicados en el array. Por ejemplo, si el array que se va a buscar fuera $[1,2,3,4,4,5,6,7]$ y el objetivo era $4$ , entonces sería correcto que el algoritmo devolviera el cuarto (índice 3) o el quinto (índice 4) elemento. El procedimiento regular devolvería el cuarto elemento (índice 3) en este caso. No siempre devuelve el primer duplicado (considere $[1,2,4,4,4,5,6,7]$ (que 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 objetivo que está duplicado en el array. 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 dicho elemento existe. ^{[ 9 ]}

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 ]}

Colocar $L$ a $0$ y $R$ a $n$ .
Mientras $L<R$ $L<R$ ,
1. Colocar $m$ (la posición del elemento central) a $L$ más el piso de ${\frac {RL}{2}}$ , que es el mayor número entero menor o igual que ${\frac {RL}{2}}$ .
2. Si $A_{m}<T$ , colocar $L$ a $m+1$ .
3. Demás, $A_{m}\geq T$ ; colocar $R$ a $m$ .
Devolver $L$ .

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

¿Dónde floorestá la función floor? El pseudocódigo para esta versión es:

función binary_search_leftmost(A, n, T): L := 0 R := n mientras L < R: m := L + piso((R - L) / 2) si A[m] < T: L := m + 1 demás : R := m regresar 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 ]}

Colocar $L$ a $0$ y $R$ a $n$ .
Mientras $L<R$ $L<R$ ,
1. Colocar $m$ (la posición del elemento central) a $L$ más el piso de ${\frac {RL}{2}}$ , que es el mayor número entero menor o igual que ${\frac {RL}{2}}$ .
2. Si $A_{m}>T$ , colocar $R$ a $m$ .
3. Demás, $A_{m}\leq T$ ; colocar $L$ a $m+1$ .
Devolver $R-1$ .

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

¿Dónde floorestá la función floor? El pseudocódigo para esta versión es:

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

Coincidencias aproximadas

{\displaystyle 5} — 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 objetivo. $5$ , que no está en el array.

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, ya que opera sobre arreglos ordenados. Por ejemplo, la búsqueda binaria se puede usar para calcular, para un valor dado, su rango (el número de elementos menores), predecesor (el siguiente elemento menor), sucesor (el siguiente elemento mayor) 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 clasificación se pueden realizar con el procedimiento para encontrar el elemento más a la izquierda . El procedimiento devuelve el número de elementos menores que el valor objetivo. ^{[ 11 ]}
Las consultas de predecesor se pueden realizar con consultas de rango. Si el rango del valor objetivo es $r$ , su predecesor es $r-1$ . ^{[ 12 ]}
Para consultas sucesoras, se puede utilizar el procedimiento para encontrar el elemento más a la derecha . Si el resultado de ejecutar el procedimiento para el valor objetivo es $r$ , entonces el sucesor del valor objetivo es $r+1$ . ^{[ 12 ]}
El vecino más cercano del valor objetivo es su predecesor o su sucesor, el que esté más cerca.
Las consultas de rango también son sencillas. ^{[ 12 ]} Una vez que se conocen las posiciones de los dos valores, la diferencia entre las posiciones es el número de elementos mayores o iguales al primer valor y menores que el segundo. Este recuento se puede ajustar en uno, ya sea hacia arriba o hacia abajo, según si los extremos del rango deben considerarse parte del mismo y si la matriz contiene entradas que coincidan con dichos extremos. ^{[ 13 ]}

Actuación

{\displaystyle [20,30,40,50,80,90,100]} — Un árbol que representa la búsqueda binaria. El array que se busca aquí es $[20,30,40,50,80,90,100]$ y el valor objetivo es $40$ .

En cuanto al número de comparaciones, el rendimiento de la búsqueda binaria se puede analizar observando la ejecución del procedimiento en un árbol binario. El nodo raíz del árbol es el elemento central del arreglo. 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 forma similar. Partiendo 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 cuestión. ^{[ 6 ]}^{[ 14 ]}

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

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

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

En el mejor de los casos, cuando el valor objetivo es el elemento central del array, 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 rendimiento 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, aumentando el número de iteraciones requeridas en el caso promedio y en 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 rendimiento promedio en todos los elementos es peor que la búsqueda binaria. Al dividir el arreglo por la mitad, la búsqueda binaria garantiza que el tamaño de ambos subarreglos sea lo más similar posible. ^{[ 14 ]}

Complejidad espacial

La búsqueda binaria requiere tres punteros a elementos, que pueden ser índices de matrices o punteros a ubicaciones de memoria, independientemente del tamaño de la matriz. Por lo tanto, la complejidad espacial de la búsqueda binaria es $O(1)$ en el modelo de computación RAM de la palabra .

Derivación del caso promedio

El número promedio de iteraciones realizadas por la 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 elementos y fuera de ellos tienen la misma probabilidad de ser buscados. El caso promedio para búsquedas exitosas es el número de iteraciones necesarias para buscar cada elemento exactamente una vez, dividido por $n$ , el número de elementos. El caso promedio para búsquedas infructuosas es el número de iteraciones necesarias para buscar un elemento dentro de cada intervalo exactamente una vez, dividido por el $n+1$ intervalos. ^{[ 14 ]}

Búsquedas exitosas

En la representación de árbol binario, una búsqueda exitosa se puede representar mediante un camino desde la raíz hasta el nodo objetivo, llamado camino interno . La longitud de un camino es el número de aristas (conexiones entre nodos) por las que pasa el camino. El número de iteraciones realizadas por una búsqueda, dado que el camino correspondiente tiene longitud $l$ , es $l+1$ contando la iteración inicial. La longitud del camino interno es la suma de las longitudes de todos los caminos internos únicos. Dado que solo hay un camino desde la raíz a cualquier nodo individual, cada camino interno representa una búsqueda de un elemento específico. Si hay $n$ elementos, que es un entero positivo, y la longitud del camino interno es $I(n)$ , entonces el número promedio de iteraciones para una búsqueda exitosa $T(n)=1+{\frac {I(n)}{n}}$ , con la iteración añadida para contar la iteración inicial. ^{[ 14 ]}

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

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

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

$\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 sería $1+{\frac {10}{7}}=2{\frac {3}{7}}$ basado en la ecuación para el caso promedio. La suma para $I(n)$ se puede simplificar a: ^{[ 14 ]}

$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 por $I(n)$ en la ecuación para $T(n)$ : ^{[ 14 ]}

$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 entero $n$ , esto es equivalente a la ecuación para el caso promedio en una búsqueda exitosa especificada anteriormente.

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 hijos, entonces se agregan nodos hijos adicionales, llamados nodos externos, de modo que cada nodo interno tenga dos hijos. Al hacer esto, 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 hasta un nodo externo. La longitud de la ruta externa es la suma de las longitudes de todas las rutas externas únicas. Si hay $n$ elementos, que es un entero positivo, y la longitud de la ruta externa es $E(n)$ , entonces el número promedio de iteraciones para una búsqueda infructuosa es $T'(n)={\frac {E(n)}{n+1}}$ , con la iteración añadida para contar la iteración inicial. La longitud de la ruta externa se divide por $n+1$ en lugar de $n$ porque hay $n+1$ rutas externas, que representan los intervalos entre y fuera de los elementos de la matriz. ^{[ 14 ]}

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

$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 por $E(n)$ en la ecuación para $T'(n)$ , se puede determinar el caso promedio de búsquedas infructuosas: ^{[ 14 ]}

$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 un procedimiento alternativo

Cada iteración del procedimiento de búsqueda binaria definido anteriormente realiza una o dos comparaciones, comprobando si el elemento central 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 comprueba si el elemento central es igual al objetivo al final de la búsqueda. En promedio, esto elimina media comparación de cada iteración. Esto reduce ligeramente el tiempo que tarda cada iteración en la mayoría de los ordenadores. Sin embargo, garantiza que la búsqueda tome el número máximo de iteraciones, añadiendo en promedio una iteración a la búsqueda. Debido a que el bucle de comparación se realiza solo ${\textstyle \lfloor \log _{2}(n)+1\rfloor }$ veces en el peor de los casos, el ligero aumento de eficiencia por iteración no compensa la iteración adicional para todos excepto para muy grandes ${\textstyle n}$ . ^{[ c ]}^{[ 18 ]}^{[ 19 ]}

Consideraciones adicionales

Coste de comparación

Al analizar el rendimiento de la búsqueda binaria, otro factor a considerar es el tiempo necesario para comparar dos elementos. Para enteros y cadenas, el tiempo requerido aumenta linealmente a medida que aumenta la longitud de codificación (generalmente el número de bits ) de los elementos. Por ejemplo, comparar un par de enteros sin signo de 64 bits requeriría comparar hasta el doble de bits que comparar un par de enteros sin signo de 32 bits. El peor caso se da cuando los enteros son iguales. Esto puede ser significativo cuando las longitudes de codificación de los elementos son grandes, como en el caso de 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 los números reales ) suele ser más costoso que comparar enteros o cadenas cortas.

La comparación rápida de números de coma flotante es posible comparándolos como enteros. Sin embargo, este tipo de comparación genera un orden total , lo que hace que cada valor de coma flotante se compare de forma diferente entre sí y consigo mismo. Esto difiere de la comparación típica, donde -0.0 debería ser igual a 0.0 y NaN no debería compararse igual a ningún otro valor, incluido él mismo. ^{[ 20 ]}^{[ 21 ]}

Predicción de ramificaciones

Según Paul Khuong, colaborador de Steel Bank Common Lisp , la búsqueda binaria produce muy pocas predicciones erróneas de ramificación a pesar de su dependencia de los datos. Esto se debe en parte a que la mayor parte se puede expresar como movimientos condicionales en lugar de ramificaciones. Lo mismo ocurre con la mayoría de los algoritmos de búsqueda logarítmica de divide y vencerás. ^{[ 22 ]}

Uso de la caché

En la mayoría de las arquitecturas de computadoras, 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 generalmente almacenan muchos menos datos que la RAM. Por lo 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. Por ejemplo, cuando se accede a un elemento de un array, este puede almacenarse junto con los elementos que se almacenan cerca de él en la RAM, lo que hace que el acceso secuencial a los elementos del array que están cerca en índice entre sí sea más rápido ( localidad de referencia ). En un array ordenado, la búsqueda binaria puede saltar a ubicaciones de memoria distantes si el array 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 arrays grandes en la mayoría de los sistemas. ^{[ 23 ]}

Paul Khuong ha señalado que la búsqueda binaria en matrices grandes (≥ 512 KiB) de tamaño exactamente potencia de dos tiende a causar un problema adicional con la implementación de las cachés de la CPU. Específicamente, el búfer de traducción anticipada (TLB) suele implementarse como una memoria direccionable por contenido (CAM), donde la "clave" generalmente son los bits menos significativos de la dirección solicitada. Al buscar en una matriz de tamaño exactamente potencia de dos, se tiende a acceder a direcciones de memoria con los mismos bits menos significativos, lo que provoca colisiones ("aliasing") con la "clave" utilizada para obtener la CAM. El TLB típico es asociativo de 4 vías, lo que significa que puede manejar como máximo cuatro direcciones que coinciden con la misma "clave", después de lo cual se produce el thrashing del TLB . (Aunque los otros niveles de caché de la CPU también utilizan una configuración similar, gestionan áreas más pequeñas con un mayor número de vías, normalmente 8 o 16, por lo que se ven menos afectados). Esto se puede evitar desplazando el punto de división de la búsqueda binaria para que divida en 31/64 ^en lugar de exactamente en el medio. ^[ 24 ^]

Búsqueda binaria frente a otros métodos

Los arreglos ordenados 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, lo que implica un tiempo considerable. ${\textstyle O(n)}$ tiempo para cada una de estas operaciones. Además, los arreglos ordenados pueden complicar el uso de la memoria, especialmente cuando los elementos se insertan con frecuencia en el arreglo. ^{[ 25 ]} Existen otras estructuras de datos que admiten una inserción y eliminación mucho más eficientes. La búsqueda binaria se puede utilizar para realizar coincidencias exactas y pertenencia a conjuntos (determinar si un valor objetivo está en una colección de valores). Existen estructuras de datos que admiten coincidencias exactas y 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 coincidencias aproximadas eficientes, generalmente realizando dichas coincidencias en ${\textstyle O(\log n)}$ tiempo independientemente del tipo o estructura de los valores mismos. ^{[ 26 ]} Además, hay algunas operaciones, como encontrar el elemento más pequeño y el más grande, que se pueden realizar de manera eficiente en un arreglo ordenado. ^{[ 11 ]}

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 en un arreglo. La búsqueda binaria es más rápida que la búsqueda lineal para arreglos ordenados, excepto si el arreglo es corto, aunque el arreglo debe estar ordenado previamente. ^{[ d ]}^{[ 28 ]} Todos los algoritmos de ordenación basados en la comparación de elementos, como quicksort y merge sort , requieren al menos ${\textstyle O(n\log n)}$ comparaciones en el peor de los casos. ^{[ 29 ]} 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 el más grande que se pueden realizar de manera eficiente en un arreglo ordenado pero no en un arreglo no ordenado. ^{[ 30 ]}

Árboles

Un árbol de búsqueda binaria es una estructura de datos de árbol binario que funciona según el principio de búsqueda binaria. Los registros del árbol están ordenados y cada registro se puede buscar mediante un algoritmo similar a la búsqueda binaria, con un tiempo promedio logarítmico. La inserción y la eliminación también requieren un tiempo promedio logarítmico en los árboles de búsqueda binaria. Esto puede ser más rápido que la inserción y eliminación en tiempo lineal de arreglos ordenados, y los árboles binarios conservan la capacidad de realizar todas las operaciones posibles en un arreglo ordenado, incluidas las consultas de rango y aproximadas. ^{[ 26 ]}^{[ 31 ]}

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 resulta en 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 de niveles posible. Excepto para los árboles de búsqueda binaria equilibrados, el árbol puede estar gravemente desequilibrado con pocos nodos internos con dos hijos, lo que resulta en que el tiempo de búsqueda promedio y en el peor de los casos se acerque a ${\textstyle n}$ comparaciones. ^{[ e ]} Los árboles de búsqueda binaria ocupan más espacio que los arreglos ordenados. ^{[ 33 ]}

Los árboles de búsqueda binaria se prestan a búsquedas rápidas en memoria externa almacenada en discos duros, ya que pueden estructurarse eficientemente en sistemas de archivos. El árbol B generaliza este método de organización de árboles. Los árboles B se utilizan frecuentemente para organizar el almacenamiento a largo plazo, como bases de datos y sistemas de archivos . ^{[ 34 ]}^{[ 35 ]}

Hashing

Para implementar arreglos asociativos , las tablas hash , una estructura de datos que asigna claves a registros mediante una función hash , son generalmente más rápidas que la búsqueda binaria en un arreglo ordenado de registros. ^{[ 36 ]} La mayoría de las implementaciones de tablas hash requieren solo un tiempo constante amortizado en promedio. ^{[ f ]}^{[ 38 ]} Sin embargo, el hashing no es útil para coincidencias aproximadas, como calcular la siguiente clave más pequeña, la siguiente clave más grande y la clave más cercana, ya que la única información que se proporciona en caso de una búsqueda fallida es que el objetivo no está presente en ningún registro. ^{[ 39 ]} 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 el más grande, se pueden realizar de manera eficiente en arreglos ordenados, pero no en tablas hash. ^{[ 26 ]}

Algoritmos de pertenencia a conjuntos

Un problema relacionado con la búsqueda es la pertenencia a un conjunto . Cualquier algoritmo que realice una búsqueda, como la búsqueda binaria, también puede utilizarse para la pertenencia a un conjunto. Existen otros algoritmos más específicos para la pertenencia a un conjunto. Un arreglo de bits es el 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 sola clave dentro del rango de claves. Los arreglos de bits son muy rápidos, requiriendo solo ${\textstyle O(1)}$ tiempo. ^{[ 40 ]} El tipo Judy1 de matriz Judy maneja claves de 64 bits de manera eficiente. ^{[ 41 ]}

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

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 arreglos ordenados. Por ejemplo, las búsquedas, las coincidencias aproximadas y las operaciones disponibles para arreglos ordenados 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 arreglos de bits . Estas estructuras de datos especializadas suelen ser más rápidas solo porque aprovechan las propiedades de las claves con un atributo determinado (generalmente claves que son enteros pequeños), y por lo tanto consumirán tiempo o espacio para las claves que carecen de ese atributo. ^{[ 26 ]} Siempre que las claves se puedan ordenar, estas operaciones siempre se pueden realizar al menos de manera eficiente en un arreglo ordenado, independientemente de las claves. Algunas estructuras, como los arreglos de Judy, utilizan una combinación de enfoques para mitigar esto, manteniendo la eficiencia y la capacidad de realizar coincidencias aproximadas. ^{[ 41 ]}

Variaciones

búsqueda binaria uniforme

La búsqueda binaria uniforme almacena, en lugar de los límites inferior y superior, la diferencia en el índice del elemento central de la iteración actual a la siguiente iteración. De antemano se calcula una tabla de búsqueda que contiene las diferencias. Por ejemplo, si el array que se va a buscar es $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]$ , el elemento central ( $m$ ) sería $6.$ En este caso, el elemento central del subconjunto izquierdo ( $[1, 2, 3, 4, 5]$ ) es $3$ y el elemento central del subconjunto derecho ( $[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 la misma cantidad. ^{[ 44 ]} Para reducir el espacio de búsqueda, el algoritmo suma o resta este cambio al í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 computadoras decimales . ^{[ 45 ]}

Búsqueda exponencial

La búsqueda exponencial extiende la búsqueda binaria a listas ilimitadas. Comienza encontrando el primer elemento con un índice que sea potencia de dos y mayor que el valor objetivo. Luego, establece ese índice como límite superior y cambia a la búsqueda binaria. Una búsqueda toma ${\textstyle \lfloor \log _{2}x+1\rfloor }$ iteraciones antes de que se inicie la búsqueda binaria y como máximo ${\textstyle \lfloor \log _{2}x\rfloor }$ iteraciones de la búsqueda binaria, donde ${\textstyle x}$ es la posición del valor objetivo. La búsqueda exponencial funciona en listas acotadas, pero solo mejora la búsqueda binaria si el valor objetivo se encuentra cerca del inicio del array. ^{[ 46 ]}

Búsqueda por interpolación

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ínimo y máximo del array, así como su longitud. Se basa en el hecho de que el punto medio no siempre es la mejor estimación. Por ejemplo, si el valor objetivo está cerca del elemento máximo del array, es probable que se encuentre cerca del final del mismo. ^{[ 47 ]}

Una función de interpolación común es la interpolación lineal . Si $A$ es el arreglo, $L,R$ son los límites inferior y superior respectivamente, y $T$ es el objetivo, entonces se estima que el objetivo es aproximadamente $(T-A_{L})/(A_{R}-A_{L})$ del camino entre $L$ y $R$ 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 de interpolación hace que... ${\textstyle O(\log \log n)}$ comparaciones. ^{[ 47 ]}^{[ 48 ]}^{[ 49 ]}

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 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. ^{[ 47 ]}

Cascada fraccionada

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

La cascada fraccionaria se desarrolló originalmente para resolver de manera eficiente diversos problemas de geometría computacional . Se ha aplicado en otros ámbitos, como la minería de datos y el enrutamiento del protocolo de Internet . ^{[ 50 ]}

Generalización a grafos

La búsqueda binaria se ha generalizado para funcionar en ciertos tipos de grafos, donde el valor objetivo se almacena en un vértice en lugar de un elemento de un array. 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 bien en qué subárbol se encontraría el objetivo. Sin embargo, esto se puede generalizar aún más de la siguiente manera: dado un grafo no dirigido con ponderación positiva y un vértice objetivo, el algoritmo aprende al consultar un vértice que es igual al objetivo, o se le proporciona una arista incidente que está en el camino más corto desde el vértice consultado hasta el objetivo. El algoritmo estándar de búsqueda binaria es simplemente el caso en que el grafo es un camino. De manera similar, los árboles de búsqueda binaria son el caso en que se proporcionan las aristas a los subárboles izquierdo o derecho cuando el vértice consultado es diferente del objetivo. Para todos los grafos no dirigidos con ponderación positiva, existe un algoritmo que encuentra el vértice objetivo en $O(\log n)$ consultas en el peor de los casos. ^{[ 52 ]}

Búsqueda binaria ruidosa

Los algoritmos de búsqueda binaria con ruido resuelven el caso en el que el algoritmo no puede comparar de forma fiable los elementos del array. Para cada par de elementos, existe una cierta probabilidad de que el algoritmo realice una comparación incorrecta. La búsqueda binaria con ruido puede encontrar la posición correcta del objetivo con una probabilidad dada que controla la fiabilidad de la posición obtenida. Cada procedimiento de búsqueda binaria con ruido debe realizar al menos $(1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}$ comparaciones en promedio, donde $H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)$ es la función de entropía binaria y $\tau$ es la probabilidad de que el procedimiento dé como resultado la posición incorrecta. ^{[ 53 ]}^{[ 54 ]}^{[ 55 ]} El problema de búsqueda binaria con ruido puede considerarse como un caso del juego de Rényi-Ulam , ^{[ 56 ]} una variante de Veinte Preguntas donde las respuestas pueden ser incorrectas. ^{[ 57 ]}

Búsqueda binaria cuántica

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

Historia

La idea de ordenar una lista de elementos para facilitar la búsqueda se remonta a la antigüedad. El ejemplo más antiguo conocido es la tablilla Inakibit-Anu de Babilonia, que data de alrededor del año 200 a . C. La tablilla contenía unos 500 números sexagesimales y sus recíprocos ordenados lexicográficamente , lo que facilitaba la búsqueda de una entrada específica. Además, se descubrieron varias listas de nombres ordenadas por su primera letra en las islas del Egeo . El Catholicon , un diccionario latino terminado en 1286 d. C., fue la primera obra en describir reglas para ordenar palabras alfabéticamente, en lugar de solo por 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 fundamental y esencial en computación. ^{[ 9 ]} En 1957, William Wesley Peterson publicó el primer método para la búsqueda por interpolación. ^{[ 9 ]}^{[ 61 ]} Todos los algoritmos de búsqueda binaria publicados funcionaban solo para arreglos 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 todos los arreglos. ^{[ 63 ]} En 1962, Hermann Bottenbruch presentó una implementación de búsqueda binaria en ALGOL 60 que colocaba 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 . ^{[ 50 ]}^{[ 64 ]}^{[ 65 ]}

Problemas de implementación

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

— Donald Knuth ^[²^]

Cuando Jon Bentley asignó la búsqueda binaria como 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, principalmente porque las implementaciones incorrectas no se ejecutaban o devolvían una respuesta errónea en casos límite excepcionales . ^{[ 66 ]} Un estudio publicado en 1988 muestra que el código correcto para ello solo se encuentra en cinco de cada veinte libros de texto. ^{[ 67 ]} Además, la propia implementación de 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 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. ^{[ 68 ]}

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

Puede producirse un bucle infinito si las condiciones de salida del bucle no están definidas correctamente. Una vez $L$ supera $R$ La búsqueda ha fallado y debe indicarse dicho fallo. Además, el bucle debe finalizar cuando se encuentre el elemento objetivo, o, en el caso de una implementación donde esta comprobación se traslade al final, deben existir comprobaciones para determinar si la búsqueda fue exitosa o fallida 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 ]}^{[ 70 ]}

Apoyo a la biblioteca

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

C proporciona la funciónbsearch() en su biblioteca estándar , que normalmente se implementa mediante búsqueda binaria, aunque el estándar oficial no lo exige. ^{[ 71 ]}
La biblioteca estándar de C++ proporciona las funciones binary_search(), lower_bound(), upper_bound()y equal_range(). ^{[ 72 ]} Usando la biblioteca C++20std::ranges , se puede aplicar sobre un rango como std::ranges::binary_search().
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(), equalRange(), lowerBound()y trisect(), que utilizan técnicas de búsqueda binaria por defecto para rangos que ofrecen acceso aleatorio. ^{[ 73 ]}
COBOL proporciona el SEARCH ALLverbo para realizar búsquedas binarias en tablas ordenadas de COBOL. ^{[ 74 ]}
El paquete de la 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 segmentos de enteros, números de punto flotante y cadenas, respectivamente. ^{[ 75 ]}
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. ^[⁷⁶^]^[⁷⁷^]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). ^{[ 78 ]}
Para Objective-C , el framework Cocoa proporciona el método en Mac OS X 10.6+. ^[⁷⁹^] El framework Core Foundation C de Apple también contiene una función. ^[⁸⁰^]NSArray-indexOfObject:inSortedRange:options:usingComparator:CFArrayBSearchValues()
Python proporciona el bisectmódulo que mantiene una lista en orden sin tener que ordenarla después de cada inserción. ^{[ 81 ]}
La clase Array de Rubybsearch incluye un método con coincidencia aproximada incorporada. ^{[ 82 ]}
La primitiva slice de Rustbinary_search() proporciona , binary_search_by(), binary_search_by_key(), y partition_point(). ^{[ 83 ]}

Véase también

Método de bisección : algoritmo para encontrar un cero de una función ; la misma idea que se usa para resolver ecuaciones en los 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 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

↑ El $O$ es la notación Big O y $\log$ es el logaritmo . En la notación Big O, la base del logaritmo no importa ya que todo logaritmo de una base dada es un factor constante de otro logaritmo de otra base. Es decir, $\log _{b}(n)=\log _{k}(n)\div \log _{k}(b)$ , dónde $\log _{k}(b)$ es una constante.
↑ Cualquier algoritmo de búsqueda basado únicamente en comparaciones puede representarse mediante un árbol de comparación binario. Una ruta interna es cualquier ruta desde la raíz hasta un nodo existente. $I$ Sea la longitud del camino interno , la suma de las longitudes de todos los caminos internos. Si cada elemento tiene la misma probabilidad de ser buscado, el caso promedio es $1+{\frac {I}{n}}$ 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, la longitud de la ruta interna $I$ debe minimizarse. Resulta que el árbol para la búsqueda binaria minimiza la longitud del camino interno. Knuth 1998 demostró que la longitud del camino externo (la longitud del camino 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 los caminos internos como longitud del camino interno $I$ está relacionado linealmente con la longitud del camino externo $E$ . Para cualquier árbol de $n$ nodos, $I=E-2n$ Cuando cada subárbol tiene un número similar de nodos, o equivalentemente, el arreglo se divide en dos mitades en cada iteración, tanto los nodos externos como sus nodos padres internos se encuentran dentro de dos niveles. Por consiguiente, la búsqueda binaria minimiza el número de comparaciones promedio, ya que su árbol de comparación tiene la menor longitud de ruta interna posible. ^{[ 14 ]}
↑ Knuth 1998 demostró en su modelo informático MIX , que Knuth diseñó como una representación de una computadora ordinaria, que el tiempo de ejecución promedio de esta variación para una búsqueda exitosa es ${\textstyle 17.5\log _{2}n+17}$ unidades de tiempo en comparación con ${\textstyle 18\log _{2}n-16}$ unidades para búsqueda binaria regular. La complejidad temporal para esta variación crece un poco más lentamente, pero a costa de una mayor complejidad inicial. ^{[ 18 ]}
↑ Knuth (1998) realizó un análisis formal del rendimiento temporal de ambos algoritmos de búsqueda. En la computadora MIX de Knuth , que él diseñó como una representación de una computadora ordinaria, la búsqueda binaria tarda en promedio ${\textstyle 18\log n-16}$ unidades de tiempo para una búsqueda exitosa, mientras que la búsqueda lineal con un nodo centinela al final de la lista toma ${\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}$ 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 centinela si ${\textstyle n>44}$ . ^{[ 14 ]}^{[ 27 ]}
↑ Insertar los valores en orden ascendente o en un patrón de clave alternada de menor a mayor dará como resultado un árbol de búsqueda binaria que maximiza el tiempo de búsqueda promedio y en el peor de los casos.^{[ 32 ]}
↑ Es posible buscar algunas implementaciones de tablas hash en tiempo constante garantizado.^{[ 37 ]}
↑ Esto se debe a que simplemente establecer todos los bits a los que apuntan las funciones hash para una clave específica puede afectar las consultas para otras claves que tienen una ubicación hash común para una o más de las funciones.^{[ 42 ]}
↑ Existen mejoras del filtro Bloom que aumentan su complejidad o admiten la eliminación; por ejemplo, el filtro cuckoo aprovecha el hash cuckoo para obtener estas ventajas.^{[ 42 ]}
↑ Es decir, matrices de longitud 1, 3, 7, 15, 31 ...^{[ 62 ]}

Citas

↑ Williams, Jr., Louis F. (22 de abril de 1976). Una modificación al método de búsqueda de medio intervalo (búsqueda binaria) . Actas de la 14.ª Conferencia del Sureste de la ACM. ACM. págs. 95–101 . doi : 10.1145/503561.503582 . Archivado del original el 12 de marzo de 2017. Recuperado el 29 de junio de 2018 .
1 2 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Búsqueda binaria".
^ Butterfield y Ngondi 2016 , pág. 46.
^ Cormen et al. 2009 , pág. 39.
↑ Weisstein, Eric W. "Búsqueda binaria" . MathWorld .
1 2 Flores, Ivan; Madpis, George (1 de septiembre de 1971). "Longitud promedio de búsqueda binaria para listas ordenadas densas" . Communications of the ACM . 14 (9): 602– 603. doi : 10.1145/362663.362752 . ISSN 0001-0782 . S2CID 43325465 .
1 2 3 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Algoritmo B".
1 2 3 4 Bottenbruch, Hermann (1 de abril de 1962). "Estructura y uso de ALGOL 60" . Journal of the 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".
1 2 3 4 5 6 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Historial y bibliografía".
^ Kasahara y Morishita 2006 , págs. 8–9.
1 2 3 Sedgewick & Wayne 2011 , §3.1, subsección "Clasificación y selección".
1 2 3 Goldman y Goldman 2008 , págs. 461–463.
↑ Sedgewick y Wayne 2011 , §3.1, subsección "Consultas de rango".
1 2 3 4 5 6 7 8 9 10 11 12 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Análisis adicional de la búsqueda binaria".
↑ Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), "Teorema B".
↑ Chang 2003 , pág. 169.
1 2 3 Knuth 1997 , §2.3.4.5 ("Longitud de la ruta").
1 2 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Ejercicio 23".
↑ Rolfe, Timothy J. (1997). "Derivación analítica de comparaciones en búsqueda binaria" . Boletín informativo ACM SIGNUM . 32 (4): 15– 19. doi : 10.1145/289251.289255 . S2CID 23752485 .
↑ Herf, Michael (diciembre de 2001). "Trucos de radix" . stereopsis: graphics .
↑ "Implementar total_cmp para f32, f64 por golddranks · Solicitud de extracción n.° 72568 · rust-lang/rust" . GitHub .– Contiene citas relevantes de IEEE 754-2008 y -2019. Incluye una implementación y explicación de un juego de palabras.
↑ " La búsqueda binaria *elimina* las predicciones erróneas de bifurcación - Paul Khuong: algo de Lisp" . pvk.ca.
↑ Khuong, Paul-Virak; Morin, Pat (2017). "Array Layouts for Comparison-Based Searching". Journal of Experimental Algorithmics . 22 . Artículo 1.3. arXiv : 1509.05053 . doi : 10.1145/3053370 . S2CID 23752485 .
↑ " La búsqueda binaria es un caso patológico para las cachés - Paul Khuong: algo de Lisp" . pvk.ca.
↑ Knuth 1997 , §2.2.2 ("Asignación secuencial").
1 2 3 4 Beame, Paul; Fich, Faith E. (2001). "Límites óptimos para el problema del predecesor y problemas relacionados" . Journal of Computer and System Sciences . 65 (1): 38– 72. doi : 10.1006/jcss.2002.1822 .
↑ Knuth 1998 , Respuestas a los ejercicios (§6.2.1) para el "Ejercicio 5".
↑ Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada").
↑ Knuth 1998 , §5.3.1 ("Clasificación por comparación mínima").
↑ Sedgewick y Wayne 2011 , §3.2 ("Tablas de símbolos ordenados").
↑ Sedgewick y Wayne 2011 , §3.2 ("Árboles de búsqueda binaria"), subsección "Métodos basados en el orden y eliminación".
↑ Knuth 1998 , §6.2.2 ("Búsqueda en árbol binario"), subsección "¿Pero qué pasa con el peor caso?".
↑ Sedgewick y Wayne 2011 , §3.5 ("Aplicaciones"), "¿Qué implementación de tabla de símbolos debo usar?".
↑ Knuth 1998 , §5.4.9 ("Discos y tambores").
↑ Knuth 1998 , §6.2.4 ("Árboles multidireccionales").
↑ Knuth 1998 , §6.4 ("Hashing").
↑ Knuth 1998 , §6.4 ("Hashing"), subsección "Historial".
^ 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 .
↑ Morin, Pat. "Tablas hash" (PDF) . pág. 1. Archivado (PDF) del original el 9 de octubre de 2022. Recuperado el 28 de marzo de 2016 .
↑ Knuth 2011 , §7.1.3 ("Trucos y técnicas bit a bit").
1 2 Silverstein, Alan, Manual de taller de Judy IV (PDF) , Hewlett-Packard , págs. 80–81 , archivado (PDF) del original el 9 de octubre de 2022
1 2 Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Filtro Cuckoo: prácticamente mejor que Bloom . Actas de la 10.ª Conferencia Internacional ACM sobre Experimentos y Tecnologías de Redes Emergentes. págs. 75–88 . doi : 10.1145/2674005.2674994 .
↑ Bloom, Burton H. (1970). "Compromisos espacio/tiempo en la codificación hash con errores permitidos". Communications of the ACM . 13 (7): 422– 426. CiteSeerX 10.1.1.641.9096 . doi : 10.1145/362686.362692 . S2CID 7931252 .
↑ Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Una variación importante".
↑ Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Algoritmo U".
↑ Moffat y Turpin 2002 , pág. 33.
1 2 3 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Búsqueda por interpolación".
↑ Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Ejercicio 22".
↑ Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). "Búsqueda por interpolación: una búsqueda log log n " . Communications of the ACM . 21 (7): 550– 553. doi : 10.1145/359545.359557 . S2CID 11089655 .
1 2 3 Chazelle, Bernard ; Liu, Ding (6 de julio de 2001). Límites inferiores para la búsqueda de intersecciones y la cascada fraccionaria en dimensiones superiores . 33.er Simposio ACM sobre Teoría de la Computación . ACM. págs. 322–329 . doi : 10.1145/380752.380818 . ISBN 978-1-58113-349-3Consultado el 30 de junio de 2018 .
↑ Chazelle, Bernard ; Liu, Ding (1 de marzo de 2004). "Límites inferiores para la búsqueda de intersecciones y la cascada fraccionaria en dimensiones superiores" (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) del original el 9 de octubre de 2022. Recuperado el 30 de junio de 2018 .
↑ 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 .
↑ Ben-Or, Michael; Hassidim, Avinatan (2008). "El algoritmo bayesiano es óptimo para la búsqueda binaria con ruido (y también bastante bueno para la computación cuántica)" (PDF) . 49.º Simposio sobre Fundamentos de la Informática . págs. 221–230 . doi : 10.1109/FOCS.2008.58 . ISBN 978-0-7695-3436-7Archivado (PDF) del original el 9 de octubre de 2022 .
↑ Pelc, Andrzej (1989). "Búsqueda con probabilidad de error conocida" . Theoretical Computer Science . 63 (2): 185– 202. doi : 10.1016/0304-3975(89)90077-7 .
↑ Rivest, Ronald L. ; Meyer, Albert R. ; Kleitman, Daniel J. ; Winklmann, K. Cómo lidiar con errores en procedimientos de búsqueda binaria . 10º Simposio ACM sobre Teoría de la Computación . doi : 10.1145/800133.804351 .
↑ Pelc, Andrzej (2002). "Juegos de búsqueda con errores: cincuenta años lidiando con mentirosos" . Theoretical Computer Science . 270 ( 1–2 ): 71–109 . doi : 10.1016/S0304-3975(01)00303-6 .
^ Rényi, Alfréd (1961). "Sobre un problema de teoría de la información". Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei . 6 : 515– 516. SEÑOR 0143666 .
↑ Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). "Complejidades cuánticas de la búsqueda ordenada, la clasificación y la distinción de elementos". Algorithmica . 34 (4): 429– 448. arXiv : quant-ph/0102078 . doi : 10.1007/s00453-002-0976-3 . S2CID 13717616 .
↑ 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 . Bibcode : 2007PhRvA..75c2335C . doi : 10.1103/PhysRevA.75.032335 . S2CID 41539957 .
↑ Grover, Lov K. (1996). Un algoritmo mecánico cuántico rápido para la búsqueda en bases de datos . 28º Simposio ACM sobre Teoría de la Computación . Filadelfia, PA. pp. 212–219 . arXiv : quant-ph/9605043 . doi : 10.1145/237814.237866 .
↑ Peterson, William Wesley (1957). "Direccionamiento para almacenamiento de acceso aleatorio". IBM Journal of Research and Development . 1 (2): 130– 146. doi : 10.1147/rd.12.0130 .
↑ "2ⁿ − 1". OEIS A000225 Archivado el 8 de junio de 2016 en Wayback Machine . Recuperado el 7 de mayo de 2016.
↑ Lehmer, Derrick (1960). "Enseñando trucos combinatorios a una computadora". Análisis combinatorio . Actas de simposios en matemáticas aplicadas. Vol. 10. págs. 180–181 . doi : 10.1090/psapm/010/0113289 . ISBN 9780821813102. SR 0113289 . {{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
↑ Chazelle, Bernard ; Guibas, Leonidas J. (1986). "Fractional cascading: I. A data structuring technique" (PDF) . Algorithmica . 1 ( 1–4 ): 133–162 . CiteSeerX 10.1.1.117.8349 . doi : 10.1007/BF01840440 . S2CID 12745042 .
↑ Chazelle, Bernard ; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF) , Algorithmica , 1 ( 1–4 ): 163–191 , doi : 10.1007/BF01840441 , S2CID 11232235
↑ Bentley 2000 , §4.1 ("El desafío de la búsqueda binaria").
↑ Pattis, Richard E. (1988). "Errores de libro de texto en búsqueda binaria". SIGCSE Bulletin . 20 : 190–194 . doi : 10.1145/52965.53012 .
↑ Bloch, Joshua (2 de junio de 2006). "Extra, extra: léalo todo: casi todas las búsquedas binarias y los algoritmos de ordenación por fusión están rotos" . Blog de investigación de Google . Archivado del original el 1 de abril de 2016. Recuperado el 21 de abril de 2016 .
↑ Ruggieri, Salvatore (2003). "Sobre el cálculo de la semisuma de dos 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) del original el 3 de julio de 2006. Recuperado el 19 de marzo de 2016 .
↑ Bentley 2000 , §4.4 ("Principios").
↑ "bsearch – búsqueda binaria en una tabla ordenada" . Especificaciones básicas de The Open Group (7.ª ed.). The Open Group . 2013. Archivado del original el 21 de marzo de 2016. Consultado el 28 de marzo de 2016 .
↑ Stroustrup 2013 , pág. 945.
↑ "std.range - Lenguaje de programación D" . dlang.org . Consultado el 29 de abril de 2020 .
↑ Unisys ( 2012), Manual de referencia de programación COBOL ANSI-85 , vol. 1, págs. 598–601
↑ "Clasificación de paquetes" . El lenguaje de programación Go . Archivado del original el 25 de abril de 2016. Consultado el 28 de abril de 2016 .
↑ "java.util.Arrays" . Documentación de Java Platform Standard Edition 8. Oracle Corporation . Archivado del original el 29 de abril de 2016. Consultado el 1 de mayo de 2016 .
↑ "java.util.Collections" . Documentación de Java Platform Standard Edition 8. Oracle Corporation . Archivado del original el 23 de abril de 2016. Consultado el 1 de mayo de 2016 .
↑ "List<T>.BinarySearch method (T)" . Microsoft Developer Network . Archivado del original el 7 de mayo de 2016. Consultado el 10 de abril de 2016 .
↑ "NSArray" . Biblioteca para desarrolladores de Mac . Apple Inc. Archivado del original el 17 de abril de 2016. Consultado el 1 de mayo de 2016 .
↑ "CFArray" . Biblioteca para desarrolladores de Mac . Apple Inc. Archivado del original el 20 de abril de 2016. Consultado el 1 de mayo de 2016 .
↑ "8.6. bisect — Algoritmo de bisección de matrices" . La biblioteca estándar de Python . Python Software Foundation. Archivado del original el 25 de marzo de 2018. Recuperado el 26 de marzo de 2018 .
↑ Fitzgerald 2015 , pág. 152.
↑ "Tipo primitivo " . La biblioteca estándar de Rust . La Fundación Rust . 2024. Consultado el 25 de mayo de 2024 .slice

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). Ruby pocket reference . Sebastopol, California: O'Reilly Media . ISBN 978-1-4919-2601-7.
Goldman, Sally A.; Goldman, Kenneth J. (2008). Guía práctica de estructuras de datos y algoritmos con 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 resumida ; versión en 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 de algoritmos y estructuras de datos del NIST: búsqueda binaria
Comparaciones y pruebas de rendimiento de diversas implementaciones de búsqueda binaria en C. Archivado el 25 de septiembre de 2019 en Wayback Machine.

[6] El $O$ es la notación Big O y $\log$ es el logaritmo . En la notación Big O, la base del logaritmo no importa ya que todo logaritmo de una base dada es un factor constante de otro logaritmo de otra base. Es decir, $\log _{b}(n)=\log _{k}(n)\div \log _{k}(b)$ , dónde $\log _{k}(b)$ es una constante.

[18] Cualquier algoritmo de búsqueda basado únicamente en comparaciones puede representarse mediante un árbol de comparación binario. Una ruta interna es cualquier ruta desde la raíz hasta un nodo existente. $I$ Sea la longitud del camino interno , la suma de las longitudes de todos los caminos internos. Si cada elemento tiene la misma probabilidad de ser buscado, el caso promedio es $1+{\frac {I}{n}}$ 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, la longitud de la ruta interna $I$ debe minimizarse. Resulta que el árbol para la búsqueda binaria minimiza la longitud del camino interno. Knuth 1998 demostró que la longitud del camino externo (la longitud del camino 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 los caminos internos como longitud del camino interno $I$ está relacionado linealmente con la longitud del camino externo $E$ . Para cualquier árbol de $n$ nodos, $I=E-2n$ Cuando cada subárbol tiene un número similar de nodos, o equivalentemente, el arreglo se divide en dos mitades en cada iteración, tanto los nodos externos como sus nodos padres internos se encuentran dentro de dos niveles. Por consiguiente, la búsqueda binaria minimiza el número de comparaciones promedio, ya que su árbol de comparación tiene la menor longitud de ruta interna posible. ^{[ 14 ]}

[21] Knuth 1998 demostró en su modelo informático MIX , que Knuth diseñó como una representación de una computadora ordinaria, que el tiempo de ejecución promedio de esta variación para una búsqueda exitosa es ${\textstyle 17.5\log _{2}n+17}$ unidades de tiempo en comparación con ${\textstyle 18\log _{2}n-16}$ unidades para búsqueda binaria regular. La complejidad temporal para esta variación crece un poco más lentamente, pero a costa de una mayor complejidad inicial. ^{[ 18 ]}

[31] Knuth (1998) realizó un análisis formal del rendimiento temporal de ambos algoritmos de búsqueda. En la computadora MIX de Knuth , que él diseñó como una representación de una computadora ordinaria, la búsqueda binaria tarda en promedio ${\textstyle 18\log n-16}$ unidades de tiempo para una búsqueda exitosa, mientras que la búsqueda lineal con un nodo centinela al final de la lista toma ${\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}}$ 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 centinela si ${\textstyle n>44}$ . ^{[ 14 ]}^{[ 27 ]}

[37] Insertar los valores en orden ascendente o en un patrón de clave alternada de menor a mayor dará como resultado un árbol de búsqueda binaria que maximiza el tiempo de búsqueda promedio y en el peor de los casos.^{[ 32 ]}

[43] Es posible buscar algunas implementaciones de tablas hash en tiempo constante garantizado.^{[ 37 ]}

[49] Esto se debe a que simplemente establecer todos los bits a los que apuntan las funciones hash para una clave específica puede afectar las consultas para otras claves que tienen una ubicación hash común para una o más de las funciones.^{[ 42 ]}

[50] Existen mejoras del filtro Bloom que aumentan su complejidad o admiten la eliminación; por ejemplo, el filtro cuckoo aprovecha el hash cuckoo para obtener estas ventajas.^{[ 42 ]}

[71] Es decir, matrices de longitud 1, 3, 7, 15, 31 ...^{[ 62 ]}

[Williams1976-1] Williams, Jr., Louis F. (22 de abril de 1976). Una modificación al método de búsqueda de medio intervalo (búsqueda binaria) . Actas de la 14.ª Conferencia del Sureste de la ACM. ACM. págs. 95–101 . doi : 10.1145/503561.503582 . Archivado del original el 12 de marzo de 2017. Recuperado el 29 de junio de 2018 .

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Binary_search"-2] 1 2 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Búsqueda binaria".

[FOOTNOTEButterfieldNgondi201646-3] Butterfield y Ngondi 2016 , pág. 46.

[FOOTNOTECormenLeisersonRivestStein200939-4] Cormen et al. 2009 , pág. 39.

[5] Weisstein, Eric W. "Búsqueda binaria" . MathWorld .

[FloresMadpis1971-7] 1 2 Flores, Ivan; Madpis, George (1 de septiembre de 1971). "Longitud promedio de búsqueda binaria para listas ordenadas densas" . Communications of the ACM . 14 (9): 602– 603. doi : 10.1145/362663.362752 . ISSN 0001-0782 . S2CID 43325465 .

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Algorithm_B"-8] 1 2 3 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Algoritmo B".

[Bottenbruch1962-9] 1 2 3 4 Bottenbruch, Hermann (1 de abril de 1962). "Estructura y uso de ALGOL 60" . Journal of the 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".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"History_and_bibliography"-10] 1 2 3 4 5 6 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Historial y bibliografía".

[FOOTNOTEKasaharaMorishita20068–9-11] Kasahara y Morishita 2006 , págs. 8–9.

[FOOTNOTESedgewickWayne2011§3.1,_subsection_"Rank_and_selection"-12] 1 2 3 Sedgewick & Wayne 2011 , §3.1, subsección "Clasificación y selección".

[FOOTNOTEGoldmanGoldman2008461–463-13] 1 2 3 Goldman y Goldman 2008 , págs. 461–463.

[FOOTNOTESedgewickWayne2011§3.1,_subsection_"Range_queries"-14] Sedgewick y Wayne 2011 , §3.1, subsección "Consultas de rango".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Further_analysis_of_binary_search"-15] 1 2 3 4 5 6 7 8 9 10 11 12 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Análisis adicional de la búsqueda binaria".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_"Theorem_B"-16] Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), "Teorema B".

[FOOTNOTEChang2003169-17] Chang 2003 , pág. 169.

[FOOTNOTEKnuth1997§2.3.4.5_("Path_length")-19] 1 2 3 Knuth 1997 , §2.3.4.5 ("Longitud de la ruta").

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Exercise_23"-20] 1 2 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Ejercicio 23".

[22] Rolfe, Timothy J. (1997). "Derivación analítica de comparaciones en búsqueda binaria" . Boletín informativo ACM SIGNUM . 32 (4): 15– 19. doi : 10.1145/289251.289255 . S2CID 23752485 .

[Herf_2001-23] Herf, Michael (diciembre de 2001). "Trucos de radix" . stereopsis: graphics .

[rust_total_cmp-24] "Implementar total_cmp para f32, f64 por golddranks · Solicitud de extracción n.° 72568 · rust-lang/rust" . GitHub .– Contiene citas relevantes de IEEE 754-2008 y -2019. Incluye una implementación y explicación de un juego de palabras.

[25] " La búsqueda binaria *elimina* las predicciones erróneas de bifurcación - Paul Khuong: algo de Lisp" . pvk.ca.

[26] Khuong, Paul-Virak; Morin, Pat (2017). "Array Layouts for Comparison-Based Searching". Journal of Experimental Algorithmics . 22 . Artículo 1.3. arXiv : 1509.05053 . doi : 10.1145/3053370 . S2CID 23752485 .

[27] " La búsqueda binaria es un caso patológico para las cachés - Paul Khuong: algo de Lisp" . pvk.ca.

[FOOTNOTEKnuth1997§2.2.2_("Sequential_Allocation")-28] Knuth 1997 , §2.2.2 ("Asignación secuencial").

[pred-29] 1 2 3 4 Beame, Paul; Fich, Faith E. (2001). "Límites óptimos para el problema del predecesor y problemas relacionados" . Journal of Computer and System Sciences . 65 (1): 38– 72. doi : 10.1006/jcss.2002.1822 .

[FOOTNOTEKnuth1998Answers_to_Exercises_(§6.2.1)_for_"Exercise_5"-30] Knuth 1998 , Respuestas a los ejercicios (§6.2.1) para el "Ejercicio 5".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table")-32] Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada").

[FOOTNOTEKnuth1998§5.3.1_("Minimum-Comparison_sorting")-33] Knuth 1998 , §5.3.1 ("Clasificación por comparación mínima").

[FOOTNOTESedgewickWayne2011§3.2_("Ordered_symbol_tables")-34] Sedgewick y Wayne 2011 , §3.2 ("Tablas de símbolos ordenados").

[FOOTNOTESedgewickWayne2011§3.2_("Binary_Search_Trees"),_subsection_"Order-based_methods_and_deletion"-35] Sedgewick y Wayne 2011 , §3.2 ("Árboles de búsqueda binaria"), subsección "Métodos basados en el orden y eliminación".

[FOOTNOTEKnuth1998§6.2.2_("Binary_tree_searching"),_subsection_"But_what_about_the_worst_case?"-36] Knuth 1998 , §6.2.2 ("Búsqueda en árbol binario"), subsección "¿Pero qué pasa con el peor caso?".

[FOOTNOTESedgewickWayne2011§3.5_("Applications"),_"Which_symbol-table_implementation_should_I_use?"-38] Sedgewick y Wayne 2011 , §3.5 ("Aplicaciones"), "¿Qué implementación de tabla de símbolos debo usar?".

[FOOTNOTEKnuth1998§5.4.9_("Disks_and_Drums")-39] Knuth 1998 , §5.4.9 ("Discos y tambores").

[FOOTNOTEKnuth1998§6.2.4_("Multiway_trees")-40] Knuth 1998 , §6.2.4 ("Árboles multidireccionales").

[FOOTNOTEKnuth1998§6.4_("Hashing")-41] Knuth 1998 , §6.4 ("Hashing").

[FOOTNOTEKnuth1998§6.4_("Hashing"),_subsection_"History"-42] Knuth 1998 , §6.4 ("Hashing"), subsección "Historial".

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

[45] Morin, Pat. "Tablas hash" (PDF) . pág. 1. Archivado (PDF) del original el 9 de octubre de 2022. Recuperado el 28 de marzo de 2016 .

[FOOTNOTEKnuth2011§7.1.3_("Bitwise_Tricks_and_Techniques")-46] Knuth 2011 , §7.1.3 ("Trucos y técnicas bit a bit").

[judyarray-47] 1 2 Silverstein, Alan, Manual de taller de Judy IV (PDF) , Hewlett-Packard , págs. 80–81 , archivado (PDF) del original el 9 de octubre de 2022

[cuckoofilter-48] 1 2 Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Filtro Cuckoo: prácticamente mejor que Bloom . Actas de la 10.ª Conferencia Internacional ACM sobre Experimentos y Tecnologías de Redes Emergentes. págs. 75–88 . doi : 10.1145/2674005.2674994 .

[51] Bloom, Burton H. (1970). "Compromisos espacio/tiempo en la codificación hash con errores permitidos". Communications of the ACM . 13 (7): 422– 426. CiteSeerX 10.1.1.641.9096 . doi : 10.1145/362686.362692 . S2CID 7931252 .

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"An_important_variation"-52] Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Una variación importante".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Algorithm_U"-53] Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Algoritmo U".

[FOOTNOTEMoffatTurpin200233-54] Moffat y Turpin 2002 , pág. 33.

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Interpolation_search"-55] 1 2 3 Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Búsqueda por interpolación".

[FOOTNOTEKnuth1998§6.2.1_("Searching_an_ordered_table"),_subsection_"Exercise_22"-56] Knuth 1998 , §6.2.1 ("Búsqueda en una tabla ordenada"), subsección "Ejercicio 22".

[57] Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). "Búsqueda por interpolación: una búsqueda log log n " . Communications of the ACM . 21 (7): 550– 553. doi : 10.1145/359545.359557 . S2CID 11089655 .

[ChazelleLiu2001-58] 1 2 3 Chazelle, Bernard ; Liu, Ding (6 de julio de 2001). Límites inferiores para la búsqueda de intersecciones y la cascada fraccionaria en dimensiones superiores . 33.er Simposio ACM sobre Teoría de la Computación . ACM. págs. 322–329 . doi : 10.1145/380752.380818 . ISBN 978-1-58113-349-3Consultado el 30 de junio de 2018 .

[ChazelleLiu2004-59] Chazelle, Bernard ; Liu, Ding (1 de marzo de 2004). "Límites inferiores para la búsqueda de intersecciones y la cascada fraccionaria en dimensiones superiores" (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) del original el 9 de octubre de 2022. Recuperado el 30 de junio de 2018 .

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

[61] Ben-Or, Michael; Hassidim, Avinatan (2008). "El algoritmo bayesiano es óptimo para la búsqueda binaria con ruido (y también bastante bueno para la computación cuántica)" (PDF) . 49.º Simposio sobre Fundamentos de la Informática . págs. 221–230 . doi : 10.1109/FOCS.2008.58 . ISBN 978-0-7695-3436-7Archivado (PDF) del original el 9 de octubre de 2022 .

[pelc1989-62] Pelc, Andrzej (1989). "Búsqueda con probabilidad de error conocida" . Theoretical Computer Science . 63 (2): 185– 202. doi : 10.1016/0304-3975(89)90077-7 .

[63] Rivest, Ronald L. ; Meyer, Albert R. ; Kleitman, Daniel J. ; Winklmann, K. Cómo lidiar con errores en procedimientos de búsqueda binaria . 10º Simposio ACM sobre Teoría de la Computación . doi : 10.1145/800133.804351 .

[64] Pelc, Andrzej (2002). "Juegos de búsqueda con errores: cincuenta años lidiando con mentirosos" . Theoretical Computer Science . 270 ( 1–2 ): 71–109 . doi : 10.1016/S0304-3975(01)00303-6 .

[65] Rényi, Alfréd (1961). "Sobre un problema de teoría de la información". Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei . 6 : 515– 516. SEÑOR 0143666 .

[66] Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). "Complejidades cuánticas de la búsqueda ordenada, la clasificación y la distinción de elementos". Algorithmica . 34 (4): 429– 448. arXiv : quant-ph/0102078 . doi : 10.1007/s00453-002-0976-3 . S2CID 13717616 .

[quantumalgo-67] 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 . Bibcode : 2007PhRvA..75c2335C . doi : 10.1103/PhysRevA.75.032335 . S2CID 41539957 .

[68] Grover, Lov K. (1996). Un algoritmo mecánico cuántico rápido para la búsqueda en bases de datos . 28º Simposio ACM sobre Teoría de la Computación . Filadelfia, PA. pp. 212–219 . arXiv : quant-ph/9605043 . doi : 10.1145/237814.237866 .

[69] Peterson, William Wesley (1957). "Direccionamiento para almacenamiento de acceso aleatorio". IBM Journal of Research and Development . 1 (2): 130– 146. doi : 10.1147/rd.12.0130 .

[70] "2ⁿ − 1". OEIS A000225 Archivado el 8 de junio de 2016 en Wayback Machine . Recuperado el 7 de mayo de 2016.

[72] Lehmer, Derrick (1960). "Enseñando trucos combinatorios a una computadora". Análisis combinatorio . Actas de simposios en matemáticas aplicadas. Vol. 10. págs. 180–181 . doi : 10.1090/psapm/010/0113289 . ISBN 9780821813102. SR 0113289 . {{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )

[73] Chazelle, Bernard ; Guibas, Leonidas J. (1986). "Fractional cascading: I. A data structuring technique" (PDF) . Algorithmica . 1 ( 1–4 ): 133–162 . CiteSeerX 10.1.1.117.8349 . doi : 10.1007/BF01840440 . S2CID 12745042 .

[74] Chazelle, Bernard ; Guibas, Leonidas J. (1986), "Fractional cascading: II. Applications" (PDF) , Algorithmica , 1 ( 1–4 ): 163–191 , doi : 10.1007/BF01840441 , S2CID 11232235

[FOOTNOTEBentley2000§4.1_("The_Challenge_of_Binary_Search")-75] Bentley 2000 , §4.1 ("El desafío de la búsqueda binaria").

[textbook-76] Pattis, Richard E. (1988). "Errores de libro de texto en búsqueda binaria". SIGCSE Bulletin . 20 : 190–194 . doi : 10.1145/52965.53012 .

[77] Bloch, Joshua (2 de junio de 2006). "Extra, extra: léalo todo: casi todas las búsquedas binarias y los algoritmos de ordenación por fusión están rotos" . Blog de investigación de Google . Archivado del original el 1 de abril de 2016. Recuperado el 21 de abril de 2016 .

[semisum-78] Ruggieri, Salvatore (2003). "Sobre el cálculo de la semisuma de dos 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) del original el 3 de julio de 2006. Recuperado el 19 de marzo de 2016 .

[FOOTNOTEBentley2000§4.4_("Principles")-79] Bentley 2000 , §4.4 ("Principios").

[80] "bsearch – búsqueda binaria en una tabla ordenada" . Especificaciones básicas de The Open Group (7.ª ed.). The Open Group . 2013. Archivado del original el 21 de marzo de 2016. Consultado el 28 de marzo de 2016 .

[FOOTNOTEStroustrup2013945-81] Stroustrup 2013 , pág. 945.

[82] "std.range - Lenguaje de programación D" . dlang.org . Consultado el 29 de abril de 2020 .

[83] Unisys ( 2012), Manual de referencia de programación COBOL ANSI-85 , vol. 1, págs. 598–601

[84] "Clasificación de paquetes" . El lenguaje de programación Go . Archivado del original el 25 de abril de 2016. Consultado el 28 de abril de 2016 .

[85] "java.util.Arrays" . Documentación de Java Platform Standard Edition 8. Oracle Corporation . Archivado del original el 29 de abril de 2016. Consultado el 1 de mayo de 2016 .

[86] "java.util.Collections" . Documentación de Java Platform Standard Edition 8. Oracle Corporation . Archivado del original el 23 de abril de 2016. Consultado el 1 de mayo de 2016 .

[87] "List<T>.BinarySearch method (T)" . Microsoft Developer Network . Archivado del original el 7 de mayo de 2016. Consultado el 10 de abril de 2016 .

[88] "NSArray" . Biblioteca para desarrolladores de Mac . Apple Inc. Archivado del original el 17 de abril de 2016. Consultado el 1 de mayo de 2016 .

[89] "CFArray" . Biblioteca para desarrolladores de Mac . Apple Inc. Archivado del original el 20 de abril de 2016. Consultado el 1 de mayo de 2016 .

[90] "8.6. bisect — Algoritmo de bisección de matrices" . La biblioteca estándar de Python . Python Software Foundation. Archivado del original el 25 de marzo de 2018. Recuperado el 26 de marzo de 2018 .

[FOOTNOTEFitzgerald2015152-91] Fitzgerald 2015 , pág. 152.

[92] "Tipo primitivo " . La biblioteca estándar de Rust . La Fundación Rust . 2024. Consultado el 25 de mayo de 2024 .slice

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ a ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ b ]

[ 17 ]

[ c ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

en

[ 25 ]

[ 26 ]

[ d ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ e ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ f ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ g ]

[ h ]

[ 43 ]

[ 44 ]

[ 45 ]

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

[ 55 ]

[ 56 ]

[ 57 ]

[ 58 ]

[ 59 ]

[ 60 ]

[ 61 ]

[ i ]

[ 63 ]

[ 64 ]

[ 65 ]

[ 66 ]

[ 67 ]

[ 68 ]

[ 69 ]

[ 70 ]

[ 71 ]

[ 72 ]

[ 73 ]

[ 74 ]

[ 75 ]

[

[

[ 78 ]

[

[

[ 81 ]

[ 82 ]

[ 83 ]

[ 27 ]

[ 32 ]

[ 37 ]

[ 42 ]

[ 62 ]