LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

Este artículo trata sobre la búsqueda de una matriz ordenada finita. Para buscar valores de funciones continuas, vea el método de bisección .

Algoritmo de búsqueda binaria

Visualización del algoritmo de búsqueda binaria donde 7 es el valor objetivo
Clase	Algoritmo de búsqueda
Estructura de datos	Formación
El peor de los casos	O (log n )
El mejor rendimiento	O (1)
Rendimiento medio	O (log n )
La peor complejidad del espacio	O (1)

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, la mitad en la que el objetivo no puede mentir se elimina y la búsqueda continúa en la mitad restante, nuevamente tomando el elemento del medio 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 la matriz.

La búsqueda binaria se ejecuta en tiempo logarítmico en el peor de los casos , haciendo$${\ displaystyle O (\ log n)} comparaciones, donde $${\ displaystyle n} es el número de elementos en la matriz, el $${\ displaystyle O}es la notación Big O , y$${\ displaystyle \ log}es el logaritmo . ^{[6] La} búsqueda binaria es más rápida que la búsqueda lineal, excepto en matrices pequeñas. Sin embargo, la matriz debe ordenarse primero para poder aplicar la búsqueda binaria. Existen estructuras de datos especializadas diseñadas para la búsqueda rápida, como las 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 más grande en la matriz en relación con el objetivo, incluso si está ausente de la matriz.

Existen numerosas variaciones de búsqueda binaria. En particular, la cascada fraccional acelera las búsquedas binarias para el mismo valor en múltiples matrices. La cascada fraccional resuelve eficientemente 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. El árbol de búsqueda binario y las estructuras de datos del árbol B se basan en la búsqueda binaria.

Algoritmo [ editar ]

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 [ editar ]

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

1. Conjunto $${\ displaystyle L} a $${\ displaystyle 0} y $${\ displaystyle R} a $${\ displaystyle n-1}.
2. Si {\ displaystyle L> R}, la búsqueda termina como no exitosa.
3. Conjunto $${\ displaystyle m}(la posición del elemento medio) al piso de$${\ displaystyle {\ frac {L + R} {2}}}, que es el mayor entero menor o igual que $${\ displaystyle {\ frac {L + R} {2}}}.
4. Si {\ displaystyle A_ {m} establecer $${\ displaystyle L} a $${\ displaystyle m + 1} y ve al paso 2.
5. Si {\ displaystyle A_ {m}> T}establecer $${\ displaystyle R} a $${\ displaystyle m-1} y ve al paso 2.
6. Ahora $${\ displaystyle A_ {m} = T}, la búsqueda está hecha; regreso$${\ displaystyle m}.

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

función binary_search (A, n, T):
    L: = 0
    R: = n - 1
    mientras que L <= R:
        m: = piso ((L + R) / 2)
        si A [m] 
            L: = m + 1
        más si A [m]> T:
            R: = m - 1
        de lo contrario :
             return m
     return sin éxito

Alternativamente, el algoritmo puede tomar el techo de$${\ displaystyle {\ frac {L + R} {2}}}, o el menor entero mayor o igual que $${\ displaystyle {\ frac {L + R} {2}}}. Esto puede cambiar el resultado si el valor objetivo aparece más de una vez en la matriz.

Procedimiento alternativo [ editar ]

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

Hermann Bottenbruch publicó la primera implementación para omitir este control en 1962. ^[8] [9]

1. Conjunto $${\ displaystyle L} a $${\ displaystyle 0} y $${\ displaystyle R} a $${\ displaystyle n-1}.
2. Mientras $${\ displaystyle L \ neq R},
   1. Conjunto $${\ displaystyle m}(la posición del elemento central) al techo de$${\ displaystyle {\ frac {L + R} {2}}}, que es el menor entero mayor o igual que $${\ displaystyle {\ frac {L + R} {2}}}.
   2. Si {\ displaystyle A_ {m}> T}establecer $${\ displaystyle R} a $${\ displaystyle m-1}.
   3. Más, $${\ displaystyle A_ {m} \ leq T}; conjunto$${\ displaystyle L} a $${\ displaystyle m}.
3. Ahora $${\ displaystyle L = R}, la búsqueda está hecha. Si$${\ displaystyle A_ {L} = T}, regreso $${\ displaystyle L}. De lo contrario, la búsqueda termina como no exitosa.

Donde ceilestá la función de techo, el pseudocódigo para esta versión es:

función binary_search_alternative (A, n, T):
    L: = 0
    R: = n - 1
    mientras que L! = R:
        m: = techo ((L + R) / 2)
        si A [m]> T:
            R: = m - 1
        más :
            L: = m
    si A [L] == T:
         devuelve L
     devuelve sin éxito

Elementos duplicados [ editar ]

El procedimiento puede devolver cualquier índice cuyo elemento sea igual al valor objetivo, incluso si hay elementos duplicados en la matriz. Por ejemplo, si la matriz a buscar era$${\ displaystyle [1,2,3,4,4,5,6,7]} y el objetivo era $${\ displaystyle 4}, entonces sería correcto que el algoritmo devuelva 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$${\ displaystyle [1,2,4,4,4,5,6,7]}que todavía devuelve el 4to 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 se duplica 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]

Procedimiento para encontrar el elemento más a la izquierda [ editar ]

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

1. Conjunto $${\ displaystyle L} a $${\ displaystyle 0} y $${\ displaystyle R} a $${\ displaystyle n}.
2. Mientras {\ displaystyle L ,
   1. Conjunto $${\ displaystyle m}(la posición del elemento medio) al piso de$${\ displaystyle {\ frac {L + R} {2}}}, que es el mayor entero menor o igual que $${\ displaystyle {\ frac {L + R} {2}}}.
   2. Si {\ displaystyle A_ {m} establecer $${\ displaystyle L} a $${\ displaystyle m + 1}.
   3. Más, $${\ displaystyle A_ {m} \ geq T}; conjunto$${\ displaystyle R} a $${\ displaystyle m}.
3. Regreso $${\ displaystyle L}.

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

Donde 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 que L 
        m: = piso ((L + R) / 2)
        si A [m] 
            L: = m + 1
        más :
            R: = m
    volver L

Procedimiento para encontrar el elemento más a la derecha [ editar ]

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

1. Conjunto $${\ displaystyle L} a $${\ displaystyle 0} y $${\ displaystyle R} a $${\ displaystyle n}.
2. Mientras {\ displaystyle L ,
   1. Conjunto $${\ displaystyle m}(la posición del elemento medio) al piso de$${\ displaystyle {\ frac {L + R} {2}}}, que es el mayor entero menor o igual que $${\ displaystyle {\ frac {L + R} {2}}}.
   2. Si {\ displaystyle A_ {m}> T}establecer $${\ displaystyle R} a $${\ displaystyle m}.
   3. Más, $${\ displaystyle A_ {m} \ leq T}; conjunto$${\ displaystyle L} a $${\ displaystyle m + 1}.
3. Regreso $${\ displaystyle L-1}.

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

Donde 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 que L 
        m: = piso ((L + R) / 2)
        si A [m]> T:
            R: = m
        más :
            L: = m + 1
    retorno L - 1

Partidos aproximados [ editar ]

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

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 usar para calcular, para un valor dado, su rango (el número de elementos más pequeños), predecesor (siguiente elemento más pequeño), sucesor (siguiente 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 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 menor que el valor objetivo. ^[11]
• Las consultas anteriores se pueden realizar con consultas de rango. Si el rango del valor objetivo es$${\ displaystyle r}, su predecesor es $${\ displaystyle r-1}. ^[12]
• Para consultas sucesivas, 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$${\ displaystyle r}, entonces el sucesor del valor objetivo es $${\ displaystyle r + 1}. ^[12]
• El vecino más cercano del valor objetivo es su predecesor o sucesor, el que esté más cerca.
• Las consultas de rango también son sencillas. ^[12] Una vez que se conocen los rangos de los dos valores, el número de elementos mayor o igual que el primer valor y menor que el segundo es la diferencia de los dos rangos. Este recuento puede ajustarse hacia arriba o hacia abajo en uno según si los puntos finales del rango deben considerarse parte del rango y si la matriz contiene entradas que coinciden con esos puntos finales. ^[13]

Rendimiento [ editar ]

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

El peor de los casos se alcanza cuando la búsqueda alcanza el nivel más profundo del árbol, mientras que el mejor caso se alcanza cuando el valor objetivo es el elemento del 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 secundario izquierdo de la raíz, y el elemento central de la mitad superior es el nodo secundario derecho de la raíz. El resto del árbol está construido de manera similar. Comenzando desde el nodo raíz, los subárboles izquierdo o derecho se atraviesan 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 hace $${\ textstyle \ lfloor \ log _ {2} (n) +1 \ rfloor} iteraciones del ciclo de comparación, donde el $${\ textstyle \ lfloor \ rfloor}la notación denota la función de piso que produce el mayor entero menor o igual que el argumento, y$${\ textstyle \ log _ {2}}es el logaritmo binario . Esto se debe a que se llega al peor de los casos cuando la búsqueda alcanza el 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 de los casos también se puede alcanzar cuando el elemento de destino no está en la matriz. Si$${\ textstyle n}es uno menos que una potencia de dos, entonces este es siempre 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 uno menos que el peor de los casos, 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 $${\ displaystyle \ lfloor \ log _ {2} (n) \ rfloor + 1- (2 ^ {\ lfloor \ log _ {2} (n) \ rfloor +1} - \ lfloor \ log _ {2} (n ) \ rfloor -2) / n}iteraciones cuando el elemento de destino está en la matriz. Esto es aproximadamente igual a$${\ displaystyle \ log _ {2} (n) -1}iteraciones Cuando el elemento de destino no está en la matriz, la búsqueda binaria hace$${\ displaystyle \ 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 es igualmente probable que se busque. ^[14]

En el mejor de los casos, donde el valor objetivo es el elemento medio de la matriz, su posición se devuelve después de una iteración. ^[dieciséis]

En términos de iteraciones, ningún algoritmo de búsqueda que funcione solo 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 posibles ya que cada nivel por encima del nivel más bajo del árbol se llena por completo. ^[a] De lo contrario, el algoritmo de búsqueda puede eliminar pocos elementos en una iteración, aumentando 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 rendimiento promedio de todos los elementos es peor que la búsqueda binaria. Al dividir la matriz por la mitad, la búsqueda binaria asegura que el tamaño de ambas subarreglas sea lo más similar posible. ^[14]

Complejidad espacial [ editar ]

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. Sin embargo, requiere al menos$${\ displaystyle \ left \ lceil \ log _ {2} (n) \ right \ rceil} bits para codificar un puntero a un elemento de una matriz con $${\ displaystyle n}elementos. ^[17] Por lo tanto, la complejidad espacial de la búsqueda binaria es$${\ displaystyle O (\ log n)}. Además, se necesita$${\ displaystyle O (n)} espacio para almacenar la matriz.

Derivación del caso promedio [ editar ]

El número promedio de iteraciones realizadas por 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 no exitosas. Se supondrá que cada elemento tiene la misma probabilidad de buscar búsquedas exitosas. Para búsquedas sin éxito, se supondrá que los intervalos entre y fuera de los elementos 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$${\ displaystyle n}, el número de elementos. El caso promedio para búsquedas sin éxito es el número de iteraciones requeridas para buscar un elemento dentro de cada intervalo exactamente una vez, dividido por el$${\ displaystyle n + 1}intervalos. ^[14]

Búsquedas exitosas [ editar ]

En la representación de árbol binario, una búsqueda exitosa se puede representar 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 longitud$${\ displaystyle l}, es $${\ displaystyle l + 1}contando la iteración inicial. La longitud de la ruta interna es la suma de las longitudes de todas las rutas internas únicas. Como solo hay una ruta desde la raíz a cualquier nodo, cada ruta interna representa una búsqueda de un elemento específico. Si hay$${\ displaystyle n} elementos, que es un número entero positivo, y la longitud de la ruta interna es $${\ displaystyle I (n)}, luego el número promedio de iteraciones para una búsqueda exitosa $${\ displaystyle T (n) = 1 + {\ frac {I (n)} {n}}}, con la única iteración agregada para contar la iteración inicial. ^[14]

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

$${\ 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 debajo de la raíz requieren dos iteraciones, y los cuatro elementos a continuación requieren tres iteraciones. En este caso, la longitud del camino interno es: ^[18]

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

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

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

Búsquedas fallidas [ editar ]

Las búsquedas sin éxito se pueden representar aumentando el árbol con nodos externos , que forman un árbol binario extendido . Si un nodo interno, o un nodo presente en el árbol, tiene menos de dos nodos secundarios, entonces se agregan nodos secundarios adicionales, llamados nodos externos, de modo que cada nodo interno tenga dos hijos. Al hacerlo, una búsqueda fallida puede representarse como una ruta a un nodo externo, cuyo elemento primario 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$${\ displaystyle n} elementos, que es un número entero positivo, y la longitud del camino externo es $${\ displaystyle E (n)}, entonces el número promedio de iteraciones para una búsqueda fallida $${\ displaystyle T '(n) = {\ frac {E (n)} {n + 1}}}, con la única iteración agregada para contar la iteración inicial. La longitud del camino externo se divide por$${\ displaystyle n + 1} en vez de $${\ displaystyle n} porque hay $${\ displaystyle n + 1}rutas externas, que representan los intervalos entre y fuera de los elementos de la matriz. ^[14]

Este problema también puede reducirse para determinar la longitud mínima de la ruta externa de todos los árboles binarios con $${\ displaystyle n}nodos Para todos los árboles binarios, la longitud de la ruta externa es igual a la longitud de la ruta interna más$${\ displaystyle 2n}. ^[18] Sustituyendo la ecuación por$${\ displaystyle I (n)}: ^[14]

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

$${\ 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 [ editar ]

Cada iteración del procedimiento de búsqueda binaria definido anteriormente hace una o dos comparaciones, verificando si el elemento central es igual al objetivo en cada iteración. Asumiendo que cada elemento tiene la misma probabilidad de ser buscado, cada iteración hace 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 la iteración en la mayoría de las computadoras. Sin embargo, garantiza que la búsqueda tome el número máximo de iteraciones, en promedio agrega una iteración a la búsqueda. Porque 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 en la eficiencia por iteración no compensa la iteración adicional para todos, pero muy grandes $${\ textstyle n}. ^{[b] [19] [20]}

Tiempo de ejecución y uso de caché [ editar ]

Al analizar el rendimiento de la búsqueda binaria, otra consideración es el tiempo requerido 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 los bits que un par de enteros sin signo de 32 bits. El peor de los casos se logra cuando los enteros son iguales. Esto puede ser significativo cuando las longitudes de codificación de los elementos son grandes, como con tipos 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 enteros o cadenas cortas.

En la mayoría de las arquitecturas de computadora, el procesador tiene un caché de hardware separado de la RAM . Dado que se encuentran dentro del propio procesador, las memorias caché son mucho más rápidas de acceder pero generalmente almacenan mucha menos información que la RAM. Por lo tanto, la mayoría de los procesadores almacenan ubicaciones de memoria a las que se ha accedido recientemente, junto con ubicaciones de memoria cercanas. Por ejemplo, cuando se accede a un elemento de la matriz, el elemento en sí puede almacenarse junto con los elementos que se almacenan 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 ( 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 (comobúsqueda lineal y sondeo lineal en tablas hash ) que acceden a elementos en secuencia. Esto aumenta ligeramente el tiempo de ejecución de la búsqueda binaria de matrices grandes en la mayoría de los sistemas. ^[21]

Búsqueda binaria versus otros esquemas [ editar ]

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, tomando $${\ textstyle O (n)}tiempo para cada una de esas operaciones. Además, las matrices ordenadas pueden complicar el uso de la memoria, especialmente cuando los elementos a menudo se insertan en la matriz. ^[22] 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 una coincidencia exacta y establecer la pertenencia (determinar si un valor objetivo está en una colección de valores). Hay estructuras de datos que admiten una coincidencia exacta más rápida y establecen la membresía. Sin embargo, a diferencia de muchos otros esquemas de búsqueda, la búsqueda binaria se puede usar para una coincidencia aproximada eficiente, generalmente realizando tales coincidencias en$${\ textstyle O (\ log n)}tiempo independientemente del tipo o estructura de los valores mismos. ^[23] Además, hay algunas operaciones, como encontrar el elemento más pequeño y más grande, que se pueden realizar de manera eficiente en una matriz ordenada. ^[11]

Búsqueda lineal [ editar ]

La búsqueda lineal es un algoritmo de búsqueda simple que verifica cada registro hasta que encuentra el valor objetivo. La búsqueda lineal se puede hacer en una lista vinculada, lo que permite una inserción y eliminación más rápidas que una matriz. La búsqueda binaria es más rápida que la búsqueda lineal de matrices ordenadas, excepto si la matriz es corta, aunque la matriz debe ordenarse de antemano. ^[c] [25] Todos los algoritmos de ordenación basados ​​en elementos de comparación, como clasificación rápida y fusión , requieren al menos$${\ textstyle O (n \ log n)}comparaciones en el peor de los casos. ^[26] 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 puede hacer de manera eficiente en una matriz ordenada pero no en una matriz sin clasificar. ^[27]

Árboles [ editar ]

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

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 se organizan en orden ordenado, y cada registro en el árbol se puede buscar usando un algoritmo similar a la búsqueda binaria, tomando un tiempo logarítmico promedio. La inserción y eliminación también requieren un tiempo logarítmico promedio en los árboles de búsqueda binarios. Esto puede ser más rápido que la inserción y eliminación de tiempo lineal de las 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. ^[23] [28]

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 equilibrados de manera imperfecta, lo que resulta en un rendimiento ligeramente peor que la búsqueda binaria. Esto incluso se aplica a los árboles de búsqueda binarios equilibrados , los árboles de búsqueda binarios 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 binarios balanceados, el árbol puede estar severamente desequilibrado con pocos nodos internos con dos hijos, lo que resulta en un tiempo de búsqueda promedio y en el peor de los casos.$${\ textstyle n}comparaciones ^[d] Los árboles de búsqueda binarios ocupan más espacio que las matrices ordenadas. ^[30]

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

Hashing [ editar ]

Para implementar matrices asociativas , las tablas hash , una estructura de datos que asigna claves a registros mediante una función hash , generalmente son más rápidas que la búsqueda binaria en una matriz ordenada de registros. ^[33] La mayoría de las implementaciones de tablas hash requieren solo un tiempo constante amortizado en promedio. ^[e] [35] Sin embargo, el hash no es útil para coincidencias aproximadas, como calcular la siguiente clave más pequeña, la más grande y la más cercana, ya que la única información dada en una búsqueda fallida es que el objetivo no está presente en ninguna grabar. ^[36]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 matrices ordenadas pero no en tablas hash. ^[23]

Establecer algoritmos de membresía [ editar ]

Un problema relacionado con la búsqueda es establecer membresía . Cualquier algoritmo que busque, como la búsqueda binaria, también se puede usar para establecer la membresía. Hay otros algoritmos que son más específicamente adecuados para la membresía establecida. 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 , y cada bit representa una sola clave dentro del rango de claves. Las matrices de bits son muy rápidas y solo requieren$${\ textstyle O (1)}hora. ^[37] El tipo Judy1 de la matriz Judy maneja claves de 64 bits de manera eficiente. ^[38]

Para obtener resultados aproximados, los filtros Bloom , otra estructura de datos probabilística basada en el hash, almacenan un conjunto de claves codificándolas utilizando una matriz de bits y múltiples funciones hash. Los filtros Bloom son mucho más eficientes en 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)}hora. Sin embargo, los filtros Bloom sufren de falsos positivos . ^{[f] [g] [40]}

Otras estructuras de datos [ editar ]

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 las 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 , intentos y matrices de bits . Estas estructuras de datos especializadas generalmente solo son más rápidas porque aprovechan las propiedades de las claves con un determinado atributo (generalmente claves que son enteros pequeños) y, por lo tanto, consumirán tiempo o espacio para las claves que carecen de ese atributo. ^[23]Siempre que se puedan ordenar las claves, estas operaciones siempre se pueden realizar al menos de manera eficiente en una matriz ordenada, independientemente de las claves. Algunas estructuras, como las matrices de Judy, usan una combinación de enfoques para mitigar esto mientras conservan la eficiencia y la capacidad de realizar una coincidencia aproximada. ^[38]

Variaciones [ editar ]

Búsqueda binaria uniforme [ editar ]

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

Artículo principal: 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 medio desde la iteración actual hasta la siguiente. Una tabla de búsqueda que contiene las diferencias se calcula de antemano. Por ejemplo, si la matriz a buscar es [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] , el elemento central ($${\ displaystyle 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 esta misma cantidad. ^[41] Para reducir el espacio de búsqueda, el algoritmo agrega o resta este cambio del índice del elemento medio. 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 . ^[42]

Búsqueda exponencial[ editar ]

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

Artículo principal: Búsqueda exponencial

La búsqueda exponencial extiende la búsqueda binaria a listas ilimitadas. Comienza por encontrar el primer elemento con un índice que es tanto una potencia de dos como mayor que el valor objetivo. Luego, establece ese índice como el límite superior y cambia a búsqueda binaria. Una búsqueda toma$${\ textstyle \ lfloor \ log _ {2} x + 1 \ rfloor} iteraciones antes de iniciar 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 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. ^[43]

Búsqueda de interpolación [ editar ]

Visualización de la búsqueda de interpolación . En este caso, no es necesario buscar 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.

Artículo principal: Búsqueda de interpolación

En lugar de calcular el punto medio, la búsqueda de interpolación estima la posición del valor objetivo, teniendo en cuenta los elementos más bajos y más altos de la matriz, así como la longitud de la matriz. Funciona sobre la base de que el punto medio no es la mejor suposició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. ^[44]

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

En la práctica, la búsqueda de interpolación es más lenta que la búsqueda binaria de matrices pequeñas, ya que la búsqueda de interpolación requiere un cálculo adicional. Su complejidad temporal crece más lentamente que la búsqueda binaria, pero esto solo compensa el cómputo adicional para matrices grandes. ^[44]

Cascada fraccional [ editar ]

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

Artículo principal: cascada fraccional

La cascada fraccional es una técnica que acelera las búsquedas binarias para el mismo elemento en múltiples arreglos ordenados. La búsqueda de cada matriz por separado requiere$${\ textstyle O (k \ log n)} tiempo, donde $${\ textstyle k}es la cantidad de matrices. La cascada fraccional reduce esto 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. ^[47] [48]

La cascada fraccional se desarrolló originalmente para resolver de manera eficiente varios problemas de geometría computacional . La cascada fraccional se ha aplicado en otros lugares, como la minería de datos y el enrutamiento del Protocolo de Internet . ^[47]

Generalización a gráficos [ editar ]

La búsqueda binaria se ha generalizado para trabajar 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 binarios 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 puede generalizarse aún más como sigue: 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 que el gráfico es una ruta. Similar, los árboles de búsqueda binaria son el caso en que los bordes de los subárboles izquierdos o derechos se dan 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$${\ displaystyle O (\ log n)}consultas en el peor de los casos. ^[49]

Ruidosa búsqueda binaria [ editar ]

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

Los ruidosos algoritmos de búsqueda binaria resuelven el caso en el que el algoritmo no puede comparar de manera confiable elementos de la matriz. Para cada par de elementos, existe una cierta probabilidad de que el algoritmo haga una 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 cedida. Cada ruidoso procedimiento de búsqueda binaria debe hacer al menos$${\ displaystyle (1- \ tau) {\ frac {\ log _ {2} (n)} {H (p)}} - {\ frac {10} {H (p)}}} comparaciones en promedio, donde $${\ displaystyle H (p) = - p \ log _ {2} (p) - (1-p) \ log _ {2} (1-p)}es la función de entropía binaria y$${\ displaystyle \ tau}es la probabilidad de que el procedimiento arroje la posición incorrecta. ^{[50] [51] [52]} El ruidoso problema de búsqueda binaria puede considerarse como un caso del juego Rényi-Ulam , ^[53] una variante de Veinte Preguntas donde las respuestas pueden estar equivocadas.