Binary Search

Binary search es un algoritmo eficiente para encontrar un elemento específico en una lista ordenada. En lugar de revisar cada elemento uno por uno (como lo haría una búsqueda lineal), la búsqueda binaria divide repetidamente el rango de búsqueda a la mitad, reduciendo drásticamente el número de comparaciones necesarias.

¿Cómo funciona?

El algoritmo sigue estos pasos:

1. Inicialización: Se definen dos índices, uno para el límite inferior (izquierda) y otro para el límite superior (derecha) de la lista.
2. Cálculo del punto medio: Se encuentra el índice medio dividiendo la suma de los límites por dos:
   medio=izquierda+derecha2\text{medio} = \frac{\text{izquierda} + \text{derecha}}{2}
3. Comparación:
   • Si el elemento en el punto medio es el objetivo, se devuelve el índice.
   • Si el objetivo es menor que el elemento en el medio, se ajusta el límite superior.
   • Si el objetivo es mayor, se ajusta el límite inferior.
4. Repetición: El proceso continúa hasta que el elemento es encontrado o los límites se cruzan (lo que indica que el elemento no está en la lista).

Ejemplo en Python

# Implementación simple de búsqueda binaria
def busqueda_binaria(lista, objetivo):
    izquierda, derecha = 0, len(lista) - 1

    while izquierda <= derecha:
        medio = (izquierda + derecha) // 2
        if lista[medio] == objetivo:
            return medio
        elif lista[medio] < objetivo:
            izquierda = medio + 1
        else:
            derecha = medio - 1
    
    return -1

# Lista ordenada
datos = [1, 3, 5, 7, 9, 11, 13, 15]
objetivo = 7
resultado = busqueda_binaria(datos, objetivo)
print(f'Elemento encontrado en el índice: {resultado}')

Complejidad Temporal

La búsqueda binaria tiene una complejidad temporal de O(log n), lo que la hace mucho más eficiente que la búsqueda lineal (O(n)) para listas grandes.

• Búsqueda lineal: Recorre cada elemento uno por uno.
• Búsqueda binaria: Corta la lista a la mitad en cada iteración.

Por ejemplo, para una lista de 1,000 elementos, la búsqueda binaria realiza un máximo de alrededor de 10 comparaciones (log2(1000)≈10log_2(1000) \approx 10).

Aplicaciones

• Búsqueda en bases de datos ordenadas: Ideal para recuperar registros rápidamente.
• Algoritmos de compresión: Optimiza la búsqueda de patrones repetidos.
• Sistemas de archivos: Facilita la localización eficiente de datos en estructuras ordenadas.