Descodificando el algoritmo de búsqueda binaria con ejemplos

Descodificando el algoritmo de búsqueda binaria

Introducción

Un algoritmo de búsqueda binaria es una técnica de búsqueda eficiente para localizar un objeto específico dentro de un conjunto de datos ordenado. Este algoritmo comienza determinando el valor medio del conjunto de datos. Compara el valor objetivo con este valor medio y puede tomar una de tres acciones posibles:

Si coinciden, la búsqueda es exitosa y se devuelve el índice del valor objetivo.
Si el valor objetivo es mayor que el elemento central, la búsqueda continúa con la mitad del conjunto de datos.
Si el valor objetivo es menor, se selecciona la mitad izquierda para una exploración adicional.

La búsqueda binaria es altamente eficiente, con una complejidad temporal de O(log n), donde n es el número de elementos en el conjunto de datos. Esto lo convierte en un método preferido para conjuntos de datos grandes donde la búsqueda lineal sería impráctica. Sin embargo, requiere que el conjunto de datos esté ordenado de antemano.

¿Qué es la búsqueda binaria?

La búsqueda binaria es un algoritmo utilizado extensivamente en informática y matemáticas que localiza un elemento específico en un conjunto de datos ordenado. Funciona dividiendo repetidamente el conjunto de datos por la mitad y comparando el valor objetivo con el valor medio hasta que se descubra el valor objetivo o se determine que está ausente.

¿Cómo funciona la búsqueda binaria?

La búsqueda binaria funciona en base a tres conceptos esenciales: datos ordenados, dividir y conquistar y reducción del área de búsqueda.

Datos ordenados

La búsqueda binaria requiere que el conjunto de datos esté ordenado en orden ascendente o descendente. La ordenación permite la comparación sistemática con el elemento medio, lo que permite al algoritmo determinar si el valor objetivo se encuentra a la izquierda o a la derecha.

Dividir y conquistar

La búsqueda binaria sigue una política de dividir y conquistar. Comienza inspeccionando el elemento medio del conjunto de datos y dividiéndolo en dos mitades. Luego se compara este elemento medio con el valor objetivo.

Si coinciden, la búsqueda es exitosa.
Si el valor objetivo es mayor que el elemento medio, la búsqueda continúa con la mitad derecha del conjunto de datos, descartando la mitad izquierda.
Si el valor objetivo es menor, la búsqueda continúa con la mitad izquierda del conjunto de datos.

Análisis de la complejidad temporal

En cada paso de la búsqueda binaria, el espacio de búsqueda se reduce a la mitad. Esto significa que solo se necesita examinar la mitad del conjunto de datos después de un paso.
Con cada paso siguiente, el área de búsqueda se reduce a la mitad.
Este método continúa hasta que se descubre el valor objetivo o el espacio de búsqueda se reduce a un conjunto de datos vacío, lo que indica la ausencia del elemento objetivo.

La complejidad temporal de la búsqueda binaria se puede analizar de la siguiente manera:

Después de un paso, el área de búsqueda es N/2, donde N es el número de elementos.
Después de dos pasos, es N/4.
Después de tres pasos, es N/8, y así sucesivamente.

Implementación de la búsqueda binaria

Pseudocódigo para la búsqueda binaria

BúsquedaBinaria(arr, objetivo):
    izquierda = 0
    derecha = longitud de arr - 1
    
    mientras izquierda <= derecha:
        medio = (izquierda + derecha) / 2
        si arr[medio] == objetivo:
            retornar medio  // Se encontró el objetivo, se devuelve su índice
        sino si arr[medio] < objetivo:
            izquierda = medio + 1
        sino:
            derecha = medio - 1
    
    retornar -1  // Objetivo no encontrado.

Implementación en Python

def busqueda_binaria(arr, objetivo):
    izquierda = 0
    derecha = len(arr) - 1

    mientras izquierda <= derecha:
        medio = (izquierda + derecha) / 2
        si arr[medio] == objetivo:
            retornar medio  # Se encontró el objetivo, se devuelve su índice
        elif arr[medio] < objetivo:
            izquierda = medio + 1
        else:
            derecha = medio - 1

    retornar -1  # Objetivo no encontrado

Manejo de casos límite y escenarios especiales

Array vacío: Si el arreglo de entrada está vacío, el algoritmo debe devolver -1 ya que no hay elementos en la búsqueda.
Objetivo no presente en el arreglo: Si el valor objetivo no se encuentra presente en el arreglo ordenado, el algoritmo devuelve -1.
Valores duplicados: La búsqueda binaria funciona bien con valores duplicados. Devolverá el índice de la primera ocurrencia del valor objetivo si existen duplicados.
Arreglo no ordenado: La búsqueda binaria asume que el arreglo de entrada está ordenado. Si el arreglo no está ordenado, el algoritmo produce resultados incorrectos. Asegúrese de ordenar el arreglo primero.
Desbordamiento entero: En algunos lenguajes de programación (como C++), usar (izquierda + derecha) / 2 para calcular el índice medio puede provocar un desbordamiento entero para valores izquierda y derecha extremadamente grandes. Usar (izquierda + (derecha-izquierda)) / 2 puede ayudar a prevenir esto.
Error de punto flotante: En lenguajes que utilizan aritmética de punto flotante (como Python), usar (izquierda + derecha) / 2 puede no ser preciso para valores izquierda y derecha grandes. En tales casos, usar izquierda + (derecha-izquierda) /2 asegura mejores resultados.

Búsqueda Binaria en Arreglos

Realizar una búsqueda binaria en un arreglo ordenado es una tarea común en programación. Aquí están los códigos de ejemplo para los enfoques recursivo e iterativo para realizar una búsqueda binaria en un arreglo ordenado.

Código de Ejemplo: Búsqueda Binaria Iterativa en Python

def binary_search(arr, target):

    left, right = 0, len(arr) - 1

    while left <= right:

        mid = (left + right) /2

        if arr[mid] == target:

            return mid  # Se encontró el objetivo, devuelve su índice

        elif arr[mid] < target:

            left = mid + 1

        else:

            right = mid - 1

    return -1  # Objetivo no encontrado

Código de Ejemplo: Búsqueda Binaria Recursiva en Python

def binary_search_recursive(arr,target, left, right):

    if left <= right:

        mid = (left + right) / 2

        if arr[mid] == target:

            return mid  # Se encontró el objetivo, devuelve su índice

        elif arr[mid] < target:

            return binary_search_recursive(arr, target, mid + 1, right)

        else:

            return binary_search_recursive(arr, target, left, mid - 1) 

    return -1  # Objetivo no encontrado

Explicación

Enfoque Iterativo

La búsqueda binaria iterativa comienza con dos punteros, izquierdo y derecho.
Entra en un bucle “while” que continúa hasta que “izquierdo” sea menor o igual a “derecho”.
Dentro del bucle, calcula el índice “medio” y verifica si el valor en “medio” es igual al objetivo.
Si se encuentra el objetivo, devuelve el índice.
Si el objetivo es menor que el elemento en “medio”, actualiza “derecho” a “medio – 1”, estrechando exitosamente la búsqueda a la mitad izquierda del arreglo.
Si el objetivo es mayor, actualiza “izquierdo” a “medio + 1”, estrechando la búsqueda a la mitad derecha.
El bucle continúa hasta que se encuentre el objetivo o “izquierdo” sea mayor que “derecho”.

Enfoque Recursivo

La búsqueda binaria recursiva toma “izquierdo” y “derecho” para definir el rango de búsqueda actual.
Verifica si “izquierdo” es menor o igual a “derecho”.
Calcula el índice “medio” y compara el elemento en “medio” con el objetivo.
Si se encuentra el objetivo, devuelve el índice.
Si el objetivo es menor que el elemento en “medio”, se llama recursivamente a sí misma con un valor actualizado de “derecho” para la mitad izquierda.
Si el objetivo es mayor, se llama recursivamente a sí misma con un valor actualizado de “izquierdo” para buscar en la mitad derecha.
La recursión continúa hasta que se encuentre el objetivo o el espacio de búsqueda esté vacío.

Búsqueda Binaria en Otras Estructuras de Datos

La búsqueda binaria es un algoritmo de búsqueda eficiente, pero su adaptación depende de la estructura de datos.

Árboles de Búsqueda Binaria (BSTs)

Los árboles de búsqueda binaria son un tipo natural para la búsqueda binaria debido a su forma. Es un árbol donde cada nodo tiene dos hijos, y el subárbol izquierdo contiene nodos con valores menores que el nodo actual, mientras que el subárbol derecho incluye nodos con valores mayores que el nodo actual. La búsqueda binaria se puede adaptar a los BSTs de la siguiente manera:

Búsqueda en un BST: Desde el nodo raíz, compara el valor objetivo con el valor actual del nodo.
Si coinciden, la búsqueda es exitosa.
Si el valor objetivo es menor, continúa la búsqueda en el subárbol izquierdo.
Si el valor objetivo es mayor, continúa la búsqueda en el subárbol derecho.

Consideraciones Especiales para los BSTs

Cuando se agregan o eliminan elementos en un BST, es importante mantener las propiedades del BST (izquierda < actual < derecha para cada nodo).
Equilibrar el árbol es esencial para asegurarse de que el árbol siga siendo eficiente. Un árbol desequilibrado puede degradarse en listas enlazadas, lo que resulta en tiempos de búsqueda pobres.

Casos de Uso

Los BST se utilizan en varias aplicaciones, incluyendo diccionarios, bases de datos y tablas de símbolos.

Arrays y Listas

La búsqueda binaria se puede adaptar a arrays y listas cuando están ordenados:

Búsqueda en un Array o Lista

Una búsqueda binaria en un array o lista es el ejemplo básico. El array o lista se trata como una secuencia de elementos, y el algoritmo continúa.

Consideraciones Especiales

La estructura de datos debe estar ordenada para que la búsqueda binaria funcione correctamente.
Asegúrese de no obtener punteros de acceso que estén fuera de límites.

Casos de Uso

La búsqueda binaria en arrays o listas se utiliza en varias aplicaciones, incluyendo la búsqueda en bases de datos ordenadas, encontrar elementos en colecciones ordenadas y optimizar algoritmos como merge sort y quicksort.

Manejo de Duplicados

El manejo de duplicados en la búsqueda binaria requiere estrategias específicas para encontrar la primera, última o todas las ocurrencias de un valor objetivo en un conjunto de datos ordenado. Para encontrar la primera ocurrencia, realice una búsqueda binaria estándar y devuelva el índice cuando se encuentre el objetivo. Y, para encontrar la última ocurrencia, modifique la búsqueda binaria continuando la búsqueda en la mitad derecha cuando se encuentre el objetivo para asegurarse de identificar la ocurrencia más a la derecha. Para encontrar todas las ocurrencias, combine ambas estrategias encontrando la primera o última ocurrencia y extendiendo la búsqueda en ambas direcciones para recopilar todos los punteros. Esto garantiza un manejo exhaustivo de duplicados en la búsqueda binaria. A continuación se muestran ejemplos de código en Python que ilustran estas técnicas para encontrar la primera, última o todas las ocurrencias:

Primera Ocurrencia

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1  # Inicializar el resultado en -1 en caso de que no se encuentre el objetivo
    
    while left <= right:
        mid = (left + right) // 2  # Usar división entera para encontrar el punto medio
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Continuar la búsqueda en la mitad izquierda para la primera ocurrencia
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Última Ocurrencia

def find_last_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1  # Inicializar el resultado en -1 en caso de que no se encuentre el objetivo
    
    while left <= right:
        mid = (left + right) // 2  # Usar división entera para encontrar el punto medio
        if arr[mid] == target:
            result = mid
            left = mid + 1  # Continuar la búsqueda dentro de la mitad derecha para la última ocurrencia
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Todas las Ocurrencias

def find_all_occurrences(arr, target):
    first_occurrence = find_first_occurrence(arr, target)
    last_occurrence = find_last_occurrence(arr, target)
    
    if first_occurrence == -1:
        return []  # Objetivo no encontrado
    else:
        return [i for i in range(first_occurrence, last_occurrence + 1)]

Variación de la Búsqueda Binaria

La Búsqueda Ternaria divide el espacio de búsqueda en tres elementos evaluando el objetivo con los elementos en dos puntos medios igualmente espaciados. Esto puede ser más eficiente cuando se trata de funciones con un solo máximo o mínimo, reduciendo el número de comparaciones.
La Búsqueda Exponencial es beneficiosa para listas ilimitadas. Comienza con pasos pequeños y aumenta exponencialmente el rango hasta encontrar un límite, luego aplica la búsqueda binaria dentro de ese rango.

Optimización de la Búsqueda Binaria

La optimización de los algoritmos de búsqueda binaria implica mejorar su crecimiento y rendimiento general. Las estrategias incluyen la Búsqueda por Saltos, que combina búsquedas lineales y binarias saltando por adelantado en pasos fijos, reduciendo las comparaciones para matrices enormes. La Búsqueda por Interpolación es otro método que estima la posición del objetivo principalmente en función de la distribución de datos, lo que lleva a una convergencia más rápida, especialmente para datos uniformemente distribuidos.

Las pruebas de rendimiento y el perfilado son vitales para optimizar la búsqueda binaria en conjuntos de datos grandes. Las herramientas de perfilado identifican cuellos de botella, ayudando a ajustar el código. Los benchmarks comparan el tiempo de ejecución del algoritmo en diferentes situaciones, guiando las optimizaciones. Estas técnicas aseguran que la búsqueda binaria funcione de manera óptima en diversas situaciones, desde bases de datos hasta desarrollo de juegos, donde la eficiencia y la rapidez son importantes.

Errores Comunes y Problemas en la Búsqueda Binaria

No verificar si los datos están ordenados: No asegurarse de que los datos estén ordenados antes de realizar una búsqueda binaria puede llevar a resultados incorrectos. Siempre verifique primero que los datos estén ordenados.
Cálculo incorrecto del punto medio: Utilizar (izquierda + derecha) / 2 para calcular el punto medio puede causar desbordamiento de enteros o problemas de precisión en algunos lenguajes. Utilice (izquierda + (derecha-izquierda)) / 2 para evitar estos problemas.
Bucles infinitos: No reemplazar correctamente los punteros (izquierda y derecha) en el bucle puede resultar en bucles infinitos. Asegúrese de actualizarlos regularmente.

Aplicaciones del Mundo Real

La búsqueda binaria es omnipresente en la informática y más allá. Se utiliza en motores de búsqueda como Google y Yahoo para la recuperación instantánea de páginas web, en bases de datos para consultas eficientes y en sistemas de archivos para una rápida recuperación de datos. Las aerolíneas lo utilizan para optimizar la reserva de asientos y desempeña un papel fundamental en los algoritmos de compresión de datos.

Bibliotecas y Módulos de Búsqueda Binaria

Muchos lenguajes de programación populares ofrecen bibliotecas o módulos integrados que ofrecen implementaciones eficientes de búsqueda binaria. En Python, el módulo “bisect” proporciona funciones como “bisect_left”, “bisect_right” y “bisect” para buscar e insertar elementos en listas ordenadas.

Estas funciones de biblioteca están optimizadas para el rendimiento y pueden ahorrar tiempo y esfuerzo al codificar algoritmos de búsqueda binaria personalizados.

Conclusión

La búsqueda binaria es un algoritmo flexible y eficiente para encontrar rápidamente elementos en estructuras de datos ordenadas. Ofrece una base para optimizar aplicaciones diversas, desde motores de búsqueda como Google y Yahoo hasta desarrollo de juegos. Al comprender sus principios y considerar variaciones y bibliotecas, los desarrolladores pueden utilizar la fortaleza de la búsqueda binaria para resolver problemas complejos de manera exitosa y rápida.

Si está interesado en conocer más sobre este tipo de algoritmos, nuestros cursos gratuitos y blogs pueden ayudarlo mucho.

Descodificando el algoritmo de búsqueda binaria con ejemplos