Búsqueda binaria: adivina un número del 1 al 100 en 7 intentos

Piensa un número del 1 al 100 y responde con honestidad. La página siempre pregunta por el número del medio de lo que queda, y nunca necesita más de 7 intentos.

Si pregunto por el 50 y me dices “es mayor”, de un solo golpe descarto del 1 al 50. Con cada respuesta, lo que queda por revisar se parte a la mitad: 100, 50, 25, 12, 6, 3, 1. Revisar uno por uno, en cambio, solo descarta un número por intento.

Esto solo funciona si los datos están ordenados. En una lista desordenada, saber que el 50 “no es” no te dice nada sobre dónde buscar después.

Con cada intento, la cantidad de números que puedes cubrir se duplica (más uno, el que preguntas). Con k intentos distingues hasta 2^k − 1 números:

Con 6 intentos llegas a 63, que no alcanza para 100; con 7 llegas a 127, que sí. La operación que responde “¿cuántas veces tengo que duplicar para llegar a tanto?” es el logaritmo en base 2: los intentos que necesitas son ⌈log₂(n + 1)⌉. Esa es la matemática del colegio trabajando.

Mueve el control. Revisar uno por uno crece igual que la lista; partir a la mitad solo suma un intento cada vez que la lista se duplica. Con un millón de datos, la diferencia es entre un millón de intentos y 20.

def buscar(lista, objetivo):
    izq, der = 0, len(lista) - 1
    while izq <= der:
        medio = (izq + der) // 2
        if lista[medio] == objetivo:
            return medio
        if lista[medio] < objetivo:
            izq = medio + 1
        else:
            der = medio - 1
    return -1

• izq y der marcan el rango que todavía puede tener el objetivo; al empezar, la lista entera.
• medio es el elemento del centro (// divide y descarta los decimales).
• Si el del medio es menor que el objetivo, todo lo de su izquierda también lo es: el rango empieza después de él. Si es mayor, termina antes.
• Si el rango se queda vacío (izq > der), el objetivo no está y se devuelve -1.

Para comprobar que lo entendiste, explícalo con tus palabras: ¿qué pasaría si la condición fuera izq < der en lugar de izq <= der? Pruébalo con una lista de un solo elemento.

• Bases de datos: sus índices son árboles que mantienen los datos ordenados y descartan partes enteras en cada paso. En vez de partir en dos, parten en cientos de ramas, pero la idea es la misma.
• Encontrar el cambio que rompió un programa: git bisect prueba la versión del medio de la historia y descarta la mitad buena o la mala, hasta dar con el cambio culpable.
• Un diccionario de papel: nadie lo lee página por página; lo abres por la mitad y decides hacia qué lado ir.

• Usarla en datos desordenados: no da error, simplemente responde mal.
• Los bordes: un + 1 o un - 1 de menos y el programa se queda en un bucle infinito o se salta el objetivo. Es el error más común al escribirla.
• En lenguajes con enteros de tamaño fijo (Java, C), (izq + der) / 2 puede desbordarse con listas enormes; por eso se escribe izq + (der - izq) / 2. En Python no pasa, porque sus enteros crecen lo que haga falta.