¿Cómo funciona el algoritmo de búsqueda binaria?

La búsqueda binaria funciona analizando un array ordenado, dividiendo sucesivamente el intervalo de búsqueda a la mitad.

1. Inicialización: Se define la frontera izquierda y derecha del intervalo de búsqueda (usualmente el inicio y el final del array).
2. Comparación: Se calcula el índice del medio del intervalo. El valor en ese índice se compara con el elemento buscado.
3. Reducción del intervalo:
   • Si el valor en el medio coincide con el buscado, el elemento se ha encontrado.
   • Si el valor en el medio es mayor que el buscado, la búsqueda continúa en la mitad izquierda del intervalo. La frontera derecha se desplaza a medio - 1.
   • Si el valor en el medio es menor que el buscado, la búsqueda continúa en la mitad derecha del intervalo. La frontera izquierda se desplaza a medio + 1.
4. Repetición: Los pasos 2 y 3 se repiten hasta que se encuentre el elemento o el intervalo de búsqueda quede vacío.

La complejidad del algoritmo es O(log n), lo cual es mucho más eficiente que la búsqueda lineal para arrays grandes.

Ejemplo de implementación en Python:

def binary_search(arr, target):
    """
    Implementación de búsqueda binaria.
    Toma un array ordenado y el valor buscado.
    Retorna el índice del elemento o -1 si no se encuentra.
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # Calcula el índice medio
        mid_val = arr[mid]      # Obtiene el valor en medio

        if mid_val == target:
            return mid  # Elemento encontrado
        elif mid_val < target:
            left = mid + 1  # El valor buscado es mayor, busca en la derecha
        else: # mid_val > target
            right = mid - 1 # El valor buscado es menor, busca en la izquierda

    return -1 # Elemento no encontrado