Algoritmo de búsqueda binaria - Binary search algorithm

Algoritmo de búsqueda binaria
Representación de búsqueda binaria.svg
Visualización del algoritmo de búsqueda binaria donde 7 es el valor objetivo
Clase Algoritmo de búsqueda
Estructura de datos Formación
Rendimiento en el peor de los casos O (log n )
Rendimiento en el mejor de los casos O (1)
Rendimiento medio O (log n )
Complejidad espacial en el peor de los casos O (1)

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

La búsqueda binaria se ejecuta en tiempo logarítmico en el peor de los casos , haciendo comparaciones, donde es el número de elementos en la matriz. La búsqueda binaria es más rápida que la búsqueda lineal, excepto para arreglos pequeños. Sin embargo, la matriz debe ordenarse primero para poder aplicar la búsqueda binaria. Existen estructuras de datos especializadas diseñadas para búsquedas rápidas, como tablas hash , que se pueden buscar de manera más eficiente que la búsqueda binaria. Sin embargo, la búsqueda binaria se puede utilizar para resolver una gama más amplia de problemas, como encontrar el elemento siguiente más pequeño o siguiente 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 fraccionada acelera las búsquedas binarias del mismo valor en varias matrices. La cascada fraccionada resuelve eficazmente 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 binaria y las estructuras de datos del árbol B se basan en la búsqueda binaria.

Algoritmo

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

Procedimiento

Dada una matriz de elementos con valores o registros ordenados de tal manera que , y el valor objetivo , la siguiente subrutina usa la búsqueda binaria para encontrar el índice de in .

  1. Establecer en y en .
  2. Si , la búsqueda termina sin éxito.
  3. Establezca (la posición del elemento del medio) en el piso de , que es el mayor número entero menor o igual que .
  4. Si , configúrelo en y vaya al paso 2.
  5. Si , configúrelo en y vaya al paso 2.
  6. Ahora , la búsqueda está hecha; volver .

Este procedimiento iterativo realiza un seguimiento de los límites de búsqueda con las dos variables y . El procedimiento puede expresarse en pseudocódigo de la siguiente manera, donde los nombres y tipos de variables siguen siendo los mismos que los anteriores, es la función de piso y se refiere a un valor específico que transmite el error de la búsqueda. floorunsuccessful

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

Alternativamente, el algoritmo puede tomar el techo de . 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 verifica si el elemento del medio ( ) es igual al objetivo ( ) en cada iteración. Algunas implementaciones omiten esta verificación durante cada iteración. El algoritmo realizaría esta verificación solo cuando queda un elemento (cuando ). 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.

Hermann Bottenbruch publicó la primera implementación para omitir este cheque en 1962.

  1. Establecer en y en .
  2. Mientras ,
    1. Establezca (la posición del elemento del medio) en el techo de , que es el menor número entero mayor o igual que .
    2. Si , establezca en .
    3. De lo contrario ,; establecido en .
  3. Ahora , la búsqueda está hecha. Si , regresa . De lo contrario, la búsqueda termina sin éxito.

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

function binary_search_alternative(A, n, T) is
    L := 0
    R := n − 1
    while L != R do
        m := ceil((L + R) / 2)
        if A[m] > T then
            R := m − 1
        else:
            L := m
    if A[L] = T then
        return L
    return unsuccessful

Elementos duplicados

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 y el objetivo era , entonces sería correcto que el algoritmo devolviera el cuarto elemento (índice 3) o el quinto elemento (índice 4). El procedimiento regular devolvería el cuarto elemento (índice 3) en este caso. No siempre devuelve el primer duplicado (considere que todavía devuelve 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 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 tal elemento existe.

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:

  1. Establecer en y en .
  2. Mientras ,
    1. Establezca (la posición del elemento del medio) en el piso de , que es el mayor número entero menor o igual que .
    2. Si , establezca en .
    3. De lo contrario ,; establecido en .
  3. Regreso .

Si y , entonces es el elemento más a la izquierda que es igual . Incluso si no está en la matriz, ¿ es el rango de en la matriz o el número de elementos en la matriz que son menores que .

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

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return 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:

  1. Establecer en y en .
  2. Mientras ,
    1. Establezca (la posición del elemento del medio) en el piso de , que es el mayor número entero menor o igual que .
    2. Si , establezca en .
    3. De lo contrario ,; establecido en .
  3. Regreso .

Si y , entonces es el elemento más a la derecha que es igual . Incluso si no está en la matriz, el número de elementos de la matriz es mayor que .

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

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

Partidos aproximados

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 , 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 utilizar para calcular, para un valor dado, su rango (el número de elementos más pequeños), predecesor (elemento más pequeño siguiente), sucesor (elemento más grande siguiente) 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.

  • Las consultas de rango 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.
  • Las consultas anteriores se pueden realizar con consultas de clasificación. Si el rango del valor objetivo es , su predecesor es  .
  • 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 , entonces el sucesor del valor objetivo es  .
  • 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. 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 se puede ajustar 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.

Rendimiento

Un árbol que representa la búsqueda binaria. La matriz que se busca aquí es , y el valor objetivo es .
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 intermedio.

En cuanto al número de comparaciones, el rendimiento de la búsqueda binaria se puede analizar viendo la ejecución del procedimiento en un árbol binario. El nodo raíz del árbol es el elemento intermedio de la matriz. El elemento del medio de la mitad inferior es el nodo hijo izquierdo de la raíz, y el elemento del medio de la mitad superior es el nodo hijo 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.

En el peor de los casos, la búsqueda binaria realiza iteraciones del ciclo de comparación, donde la notación denota la función de piso que produce el mayor número entero menor o igual que el argumento, y es el logaritmo binario . Esto se debe a que se alcanza el peor de los casos cuando la búsqueda alcanza el nivel más profundo del árbol, y siempre hay niveles en el árbol para cualquier búsqueda binaria.

También se puede llegar al peor de los casos cuando el elemento de destino no está en la matriz. Si es uno menos que una potencia de dos, entonces este es siempre el caso. De lo contrario, la búsqueda puede realizar iteraciones si la búsqueda alcanza el nivel más profundo del árbol. Sin embargo, puede realizar iteraciones, que es una menos que en el peor de los casos, si la búsqueda termina en el segundo nivel más profundo del árbol.

En promedio, asumiendo que cada elemento tiene la misma probabilidad de ser buscado, la búsqueda binaria realiza iteraciones cuando el elemento de destino está en la matriz. Esto es aproximadamente igual a las iteraciones. Cuando el elemento de destino no está en la matriz, la búsqueda binaria realiza iteraciones en promedio, asumiendo que el rango entre elementos y elementos externos es igualmente probable que se busque.

En el mejor de los casos, cuando el valor objetivo es el elemento medio de la matriz, su posición se devuelve después de una iteración.

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. 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 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 de todos los elementos es peor que la búsqueda binaria. Al dividir el arreglo por la mitad, la búsqueda binaria asegura que el tamaño de ambos subarreglos sea lo más similar posible.

Complejidad espacial

La búsqueda binaria requiere tres punteros a elementos, que pueden ser índices de matriz o punteros a ubicaciones de memoria, independientemente del tamaño de la matriz. Por lo tanto, la complejidad espacial de la búsqueda binaria está en el modelo de cálculo RAM de palabras .

Derivación de caso promedio

El número medio 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 no exitosas. Se supondrá que cada elemento tiene la misma probabilidad de ser buscado para búsquedas exitosas. Para búsquedas infructuosas, se asumirá que los intervalos entre elementos externos y entre elementos tienen la misma probabilidad de ser buscados. El caso promedio de búsquedas exitosas es el número de iteraciones necesarias para buscar cada elemento exactamente una vez, dividido por el número de elementos. El caso promedio de búsquedas fallidas es el número de iteraciones necesarias para buscar un elemento dentro de cada intervalo exactamente una vez, dividido por los intervalos.

Búsquedas exitosas

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, denominada ruta interna . La longitud de una ruta es el número de bordes (conexiones entre nodos) por los que pasa la ruta. El número de iteraciones realizadas por una búsqueda, dado que la ruta correspondiente tiene longitud , está contando la iteración inicial. La longitud de la ruta interna es la suma de las longitudes de todas las rutas internas únicas. Dado que solo hay una ruta desde la raíz a un solo nodo, cada ruta interna representa una búsqueda de un elemento específico. Si hay elementos, que es un número entero positivo, y la longitud de la ruta interna es , entonces el número promedio de iteraciones para una búsqueda exitosa , con la iteración agregada para contar la iteración inicial.

Dado que la búsqueda binaria es el algoritmo óptimo para la búsqueda con comparaciones, este problema se reduce a calcular la longitud de ruta interna mínima de todos los árboles binarios con nodos, que es igual a:

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 siguientes requieren tres iteraciones. En este caso, la longitud de la ruta interna es:

El número promedio de iteraciones se basaría en la ecuación para el caso promedio. La suma de se puede simplificar a:

Sustituyendo la ecuación por en la ecuación por :

Para entero , 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 secundarios, entonces se agregan nodos secundarios adicionales, llamados nodos externos, para que cada nodo interno tenga dos secundarios. Al hacerlo, una búsqueda fallida se puede representar como una ruta a un nodo externo, cuyo padre es el elemento único 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 elementos, que es un número entero positivo, y la longitud de la ruta externa es , entonces el número promedio de iteraciones para una búsqueda fallida , con la iteración agregada para contar la iteración inicial. La longitud de la ruta externa se divide por en lugar de porque hay rutas externas, que representan los intervalos entre y fuera de los elementos de la matriz.

De manera similar, este problema se puede reducir a la determinación de la longitud de ruta externa mínima de todos los árboles binarios con nodos. Para todos los árboles binarios, la longitud de la ruta externa es igual a la longitud de la ruta interna más . Sustituyendo la ecuación por :

Sustituyendo la ecuación de en la ecuación de , se puede determinar el caso promedio de búsquedas fallidas:

Realización de procedimiento alternativo

Cada iteración del procedimiento de búsqueda binaria definido anteriormente hace una o dos comparaciones, verificando si el elemento del medio es igual al objetivo en cada iteración. Suponiendo que cada elemento tiene la misma probabilidad de ser buscado, cada iteración 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 necesario por iteración en la mayoría de las computadoras. Sin embargo, garantiza que la búsqueda tome el número máximo de iteraciones, agregando en promedio una iteración a la búsqueda. Debido a que el ciclo de comparación se realiza solo veces en el peor de los casos, el ligero aumento en la eficiencia por iteración no compensa la iteración adicional para todos, excepto para los muy grandes .

Tiempo de ejecución y uso de caché

Al analizar el rendimiento de la búsqueda binaria, otra consideración es el tiempo necesario para comparar dos elementos. Para 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 de los casos se logra cuando los números enteros son iguales. Esto puede ser significativo cuando las longitudes de codificación de los elementos son grandes, como con tipos de enteros grandes o cadenas largas, lo que hace que comparar elementos sea costoso. 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 una caché de hardware separada de la RAM . Dado que se encuentran dentro del propio procesador, los cachés son mucho más rápidos de acceder, pero por lo general almacenan muchos menos datos 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 agiliza el acceso secuencial a los elementos de la matriz que están cerca en índice entre sí ( localidad de referencia ) . En una matriz ordenada, la búsqueda binaria puede saltar a ubicaciones de memoria distantes si la matriz es grande, a diferencia de los algoritmos (como la búsqueda lineal y el sondeo lineal en tablas hash ) que acceden a los elementos en secuencia. Esto aumenta ligeramente el tiempo de ejecución de la búsqueda binaria para matrices grandes en la mayoría de los sistemas.

Búsqueda binaria versus otros esquemas

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 lleva tiempo para cada una de estas operaciones. Además, las matrices ordenadas pueden complicar el uso de la memoria, especialmente cuando los elementos se insertan a menudo en la matriz. Hay 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 establecer la pertenencia (determinando 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 una pertenencia a conjuntos. Sin embargo, a diferencia de muchos otros esquemas de búsqueda, la búsqueda binaria se puede utilizar para una coincidencia aproximada eficiente, generalmente realizando dichas coincidencias en el tiempo independientemente del tipo o estructura de los valores en sí. 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.

Búsqueda lineal

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 realizar en una lista vinculada, lo que permite una inserción y eliminación más rápida que una matriz. La búsqueda binaria es más rápida que la búsqueda lineal de matrices ordenadas, excepto si la matriz es corta, aunque la matriz debe ordenarse de antemano. Todos los algoritmos de clasificación basados ​​en la comparación de elementos, como la clasificación rápida y la clasificación por combinación , requieren al menos comparaciones en el peor de los casos. A diferencia de la búsqueda lineal, la búsqueda binaria se puede utilizar para una coincidencia aproximada eficiente. Hay operaciones como encontrar el elemento más pequeño y más grande que se pueden realizar de manera eficiente en una matriz ordenada, pero no en una matriz no ordenada.

Árboles

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 están ordenados por orden, 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 árboles de búsqueda binaria. Esto puede ser más rápido que la inserción y eliminación de tiempo lineal de matrices ordenadas, y los árboles binarios conservan la capacidad de realizar todas las operaciones posibles en una matriz ordenada, incluidas las consultas de rango y aproximadas.

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 mal equilibrados, lo que resultará en un rendimiento ligeramente peor que la búsqueda binaria. Esto se aplica incluso a los árboles de búsqueda binarios equilibrados , árboles de búsqueda binarios que equilibran sus propios nodos, porque rara vez producen el árbol con la menor cantidad de niveles posibles. A excepción de los árboles de búsqueda binarios equilibrados, el árbol puede estar gravemente desequilibrado con pocos nodos internos con dos hijos, lo que hace que el tiempo de búsqueda promedio y el peor de los casos se acerquen a las comparaciones. Los árboles de búsqueda binaria ocupan más espacio que las matrices ordenadas.

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

Hashing

Para implementar matrices asociativas , las tablas hash , una estructura de datos que asigna claves a registros usando una función hash , son generalmente más rápidas que la búsqueda binaria en una matriz ordenada de registros. La mayoría de las implementaciones de tablas hash requieren solo un tiempo constante amortizado en promedio. Sin embargo, el hash no es útil para coincidencias aproximadas, como calcular la siguiente clave más pequeña, la siguiente más grande y la más cercana, ya que la única información proporcionada en una búsqueda fallida es que el objetivo no está presente en ningún registro. La búsqueda binaria es ideal para este tipo de 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.

Establecer algoritmos de membresía

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

Para obtener resultados aproximados, los filtros Bloom , otra estructura de datos probabilística basada en hash, almacenan un conjunto de claves codificando las claves usando una matriz de bits y múltiples funciones hash. Los filtros Bloom son mucho más eficientes en el espacio que las matrices de bits en la mayoría de los casos y no mucho más lentos: con las funciones hash, las consultas de membresía solo requieren tiempo. Sin embargo, los filtros Bloom sufren de falsos positivos .

Otras estructuras de datos

Existen estructuras de datos que pueden mejorar la búsqueda binaria en algunos casos tanto para la búsqueda como para otras operaciones disponibles para matrices ordenadas. Por ejemplo, las búsquedas, 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 , intentos y arreglos de bits . Estas estructuras de datos especializadas suelen ser más rápidas porque aprovechan las propiedades de las claves con un determinado atributo (generalmente claves que son números enteros pequeños) y, por lo tanto, consumirán tiempo o espacio para las claves que carecen de ese atributo. 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, utilizan una combinación de enfoques para mitigar esto mientras conservan la eficiencia y la capacidad de realizar una coincidencia aproximada.

Variaciones

Búsqueda binaria uniforme

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

La búsqueda binaria uniforme almacena, en lugar de los límites superior e inferior, la diferencia en el índice del elemento intermedio desde la iteración actual hasta la siguiente. Se calcula de antemano una tabla de búsqueda que contiene las diferencias. Por ejemplo, si la matriz que se buscará es [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] , el elemento del medio ( ) sería 6 . En este caso, el elemento del medio del subarreglo izquierdo ( [1, 2, 3, 4, 5] ) es 3 y el elemento del medio del subarreglo 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. Para reducir el espacio de búsqueda, el algoritmo suma o resta este cambio del índice del elemento intermedio. La búsqueda binaria uniforme puede ser más rápida en sistemas donde no es eficiente calcular el punto medio, como en computadoras decimales .

Búsqueda exponencial

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

La búsqueda exponencial extiende la búsqueda binaria a listas ilimitadas. Comienza por encontrar el primer elemento con un índice que sea a la vez una potencia de dos y mayor que el valor objetivo. Luego, establece ese índice como el límite superior y cambia a la búsqueda binaria. Una búsqueda toma iteraciones antes de que se inicie la búsqueda binaria y en la mayoría de las iteraciones de la búsqueda binaria, donde es la posición del valor objetivo. La búsqueda exponencial funciona en listas delimitadas, 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.

Búsqueda de interpolación

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

En lugar de calcular el punto medio, la búsqueda 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.

Una función de interpolación común es la interpolación lineal . Si es la matriz, son los límites inferior y superior respectivamente, y es el objetivo, se estima que el objetivo se encuentra aproximadamente entre y . Cuando se utiliza la interpolación lineal y la distribución de los elementos de la matriz es uniforme o casi uniforme, la búsqueda de interpolación hace comparaciones.

En la práctica, la búsqueda por interpolación es más lenta que la búsqueda binaria para arreglos pequeños, ya que la búsqueda por interpolación requiere cálculos adicionales. Su complejidad de tiempo crece más lentamente que la búsqueda binaria, pero esto solo compensa el cálculo adicional para arreglos grandes.

Cascada fraccionada

En cascada fraccionada , 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.

La cascada fraccionada es una técnica que acelera las búsquedas binarias del mismo elemento en varias matrices ordenadas. La búsqueda de cada matriz por separado requiere tiempo, donde está el número de matrices. La cascada fraccionada reduce esto al almacenar información específica en cada matriz sobre cada elemento y su posición en las otras matrices.

La cascada fraccionada se desarrolló originalmente para resolver de manera eficiente varios problemas de geometría computacional . La cascada fraccionada se ha aplicado en otros lugares, como en la minería de datos y el enrutamiento de protocolo de Internet .

Generalización a gráficos

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 binaria son una de esas generalizaciones: cuando se consulta un vértice (nodo) en el árbol, el algoritmo aprende que el vértice es el objetivo o, de lo contrario, en qué subárbol se ubicaría el objetivo. Sin embargo, esto se puede generalizar aún más como siguiente: 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 al objetivo. El algoritmo de búsqueda binaria estándar es simplemente el caso en el que el gráfico es una ruta. De manera similar, los árboles de búsqueda binaria son el caso en el que los bordes de los subárboles izquierdo o derecho se dan cuando el vértice consultado no es igual al objetivo. Para todos los gráficos no dirigidos y ponderados positivamente, existe un algoritmo que encuentra el vértice de destino en las consultas en el peor de los casos.

Búsqueda binaria ruidosa

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

Los algoritmos de búsqueda binaria ruidosos resuelven el caso en el que el algoritmo no puede comparar elementos de la matriz de manera confiable. Para cada par de elementos, existe una cierta probabilidad de que el algoritmo realice 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 procedimiento de búsqueda binaria ruidoso debe hacer al menos comparaciones en promedio, donde es la función de entropía binaria y es la probabilidad de que el procedimiento arroje la posición incorrecta. El problema de la búsqueda binaria ruidosa se puede considerar como un caso del juego Rényi-Ulam , una variante de Veinte preguntas donde las respuestas pueden estar equivocadas.

Búsqueda binaria cuántica

Las computadoras clásicas están limitadas al peor de los casos de iteraciones exactas 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 consultas (que representan iteraciones del procedimiento clásico), pero el factor constante es menor que uno, lo que proporciona una menor complejidad de tiempo en las computadoras cuánticas . Cualquier procedimiento de búsqueda binaria cuántica exacta , es decir, un procedimiento que siempre produce el resultado correcto, requiere al menos consultas en el peor de los casos, donde está el logaritmo natural . Existe un procedimiento de búsqueda binario cuántico exacto que se ejecuta en consultas en el peor de los casos. En comparación, el algoritmo de Grover es el algoritmo cuántico óptimo para buscar una lista desordenada de elementos y requiere consultas.

Historia

La idea de ordenar una lista de elementos para permitir una búsqueda más rápida se remonta a la antigüedad. El primer ejemplo conocido fue la tablilla Inakibit-Anu de Babilonia que se remonta a c.  200 a . C. La tableta contenía alrededor de 500 números sexagesimales y sus recíprocos ordenados en orden lexicográfico , lo que facilitó la búsqueda de una entrada específica. Además, en las islas del Egeo se descubrieron varias listas de nombres ordenados por su primera letra . Catholicon , un diccionario de latín terminado en 1286 EC, fue el primer trabajo que describió las reglas para clasificar las palabras en orden alfabético, a diferencia de las primeras letras.

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 fundamental en informática. En 1957, William Wesley Peterson publicó el primer método de búsqueda por interpolación. Cada algoritmo de búsqueda binaria publicado funcionó solo para matrices cuya longitud es uno menos que una potencia de dos hasta 1960, cuando Derrick Henry Lehmer publicó un algoritmo de búsqueda binaria que funcionó en todas las matrices. En 1962, Hermann Bottenbruch presentó una implementación ALGOL 60 de búsqueda binaria que colocó la comparación de igualdad al final , aumentando el número promedio de iteraciones en uno, pero reduciendo a uno el número de comparaciones por iteración. La búsqueda binaria uniforme fue desarrollada por AK Chandra de la Universidad de Stanford en 1971. En 1986, Bernard Chazelle y Leonidas J. Guibas introdujeron la cascada fraccionada como un método para resolver numerosos problemas de búsqueda en geometría computacional .

Problemas de implementación

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

Cuando Jon Bentley asignó la búsqueda binaria como un problema en un curso para programadores profesionales, descubrió que el noventa por ciento no pudo proporcionar una solución correcta después de varias horas de trabajar en ella, principalmente porque las implementaciones incorrectas no se ejecutaron o devolvieron una respuesta incorrecta en raras ocasiones. casos de borde . Un estudio publicado en 1988 muestra que solo se encuentra un código preciso en cinco de veinte libros de texto. Además, la propia implementación de Bentley de la búsqueda binaria, publicada en su libro Programming Pearls de 1986 , contenía un error de desbordamiento que no se detectó durante más de veinte años. La implementación de la biblioteca del lenguaje de programación Java de la búsqueda binaria tuvo el mismo error de desbordamiento durante más de nueve años.

En una implementación práctica, las variables utilizadas para representar los índices serán a menudo 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 , entonces el valor de puede exceder el rango de números enteros del tipo de datos utilizado para almacenar el punto medio, incluso si y están dentro del rango. Si y no son negativos, esto se puede evitar calculando el punto medio como .

Puede producirse un bucle infinito si las condiciones de salida del bucle no se definen correctamente. Una vez superada , la búsqueda ha fallado y debe trasmitir el fracaso de la búsqueda. Además, se debe salir del bucle cuando se encuentra el elemento de destino, o en el caso de una implementación en la que esta verificación se mueve al final, se debe verificar 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.

Soporte de biblioteca

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

  • C proporciona la función bsearch() en su biblioteca estándar , que generalmente se implementa mediante búsqueda binaria, aunque el estándar oficial no lo requiere.
  • C ++ 's Biblioteca de plantillas estándar proporciona las funciones binary_search(), lower_bound(), upper_bound()y equal_range().
  • D biblioteca estándar 's Fobos, en el std.rangemódulo proporciona un tipo SortedRange(devuelto por sort()y assumeSorted()funciones) con los métodos contains(), equaleRange(), lowerBound()y trisect(), que utilizan técnicas de búsqueda binarios de forma predeterminada para las gamas que ofrecen acceso aleatorio.
  • COBOL proporciona el SEARCH ALLverbo para realizar búsquedas binarias en tablas ordenadas COBOL.
  • Go 's sortpaquete de la biblioteca estándar contiene las funciones Search, SearchInts, SearchFloat64sy SearchStrings, que implementan búsqueda binaria en general, así como implementaciones específicas para la búsqueda de rebanadas de números enteros, números de punto flotante y cadenas, respectivamente.
  • Java ofrece un conjunto de métodos estáticos sobrecargados binarySearch() en las clases Arraysy Collectionsen el java.utilpaquete estándar para realizar búsquedas binarias en matrices Java y en Lists, respectivamente.
  • 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).
  • Para Objective-C , el marco Cocoa proporciona el NSArray -indexOfObject:inSortedRange:options:usingComparator:método en Mac OS X 10.6+. El marco Core Foundation C de Apple también contiene una CFArrayBSearchValues()función.
  • Python proporciona el bisectmódulo.
  • La clase Array de Ruby incluye un bsearchmétodo con coincidencia aproximada incorporada.

Ver también

notas y referencias

Este artículo se envió a WikiJournal of Science para su revisión por pares académicos externos 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 del expediente 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

Citas

Fuentes

enlaces externos