¿Qué algoritmo tiene una complejidad logarítmica O(log n)?

El algoritmo de búsqueda binaria (o dicotómica) tiene una complejidad temporal logarítmica O(log n).

Principio de funcionamiento de la búsqueda binaria:

1. Requiere un array (o lista) ordenado.
2. En cada paso, compara el elemento buscado con el elemento en el medio del rango de búsqueda actual.
3. Si los elementos coinciden, la búsqueda termina.
4. Si el elemento buscado es menor que el medio, la búsqueda continúa en la mitad izquierda del rango.
5. Si el elemento buscado es mayor que el medio, la búsqueda continúa en la mitad derecha del rango.
6. El rango de búsqueda se reduce a la mitad en cada paso.

Ejemplo de implementación en Python:

# Función de búsqueda binaria
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_val = arr[mid]

        if mid_val == target:
            return mid  # Elemento encontrado, devuelve el índice
        elif mid_val < target:
            low = mid + 1  # Ignora la mitad izquierda
        else:
            high = mid - 1  # Ignora la mitad derecha

    return -1  # Elemento no encontrado

# Ejemplo de uso
# lista_ordenada = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# valor_objetivo = 23
# resultado = binary_search(lista_ordenada, valor_objetivo)
# if resultado != -1:
#     print(f"Elemento encontrado en el índice: {resultado}")
# else:
#     print("Elemento no encontrado")

La complejidad logarítmica se debe a que la cantidad de operaciones es proporcional al logaritmo del tamaño de los datos de entrada (n), ya que en cada paso, el espacio de búsqueda se reduce a la mitad.