Medio · búsqueda

Búsqueda binaria

Un millón de números ordenados, veinte intentos. La búsqueda binaria es el algoritmo con mejor relación esfuerzo-beneficio de todo el conjunto, y el que más veces se escribe mal sin darse cuenta.

En una fraseMantén lo y hi, parte el rango con mid = (lo + hi) / 2 y devuelve el índice base 0 o -1: el array viene ordenado, así que O(log n) sustituye al recorrido lineal.

El problema

Entrada: La primera línea es un entero n (1 ≤ n ≤ 10000). La segunda línea contiene n enteros en orden estrictamente creciente, separados por espacios. La tercera línea es el valor x que hay que encontrar.

Salida: El índice de x empezando en 0, o -1 si no está.

Ejemplos:

Entrada	Salida
`5 1 3 5 8 9 8`	`3`
`5 1 3 5 8 9 7`	`-1`
`1 42 42`	`0`

Un bucle de 0 a n−1 también da la respuesta correcta, pero mira hasta 10000 números donde la búsqueda binaria mira unos 14. Las pruebas son pequeñas; lo que importa es el hábito.

Tu solución

main.cpp — tu solución

Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — Piensa un número entre 1 y 100

Dices 50, yo digo "más alto" y al instante sabes que la respuesta no está en 1–50. Acabas de borrar la mitad de las posibilidades con una pregunta. Ese es todo el algoritmo; lo único que añade el ordenador es hacerlo con índices exactos.

Pista 2 — Dos punteros que se acercan

Mantén lo y hi como el rango inclusivo que aún podría contener x. Mira mid = (lo + hi) / 2. Si a[mid] es demasiado pequeño, todo lo que hay a su izquierda también lo es, así que lo = mid + 1. Si es demasiado grande, hi = mid - 1. Si coincide, has terminado.

Pista 3 — Lo difícil es la condición del bucle

Usa while (lo <= hi), no lo < hi. Con <, un rango de exactamente un elemento nunca se examina, así que n = 1 siempre responde −1 aunque el número esté ahí. Y nunca escribas hi = mid: con lo <= hi eso puede entrar en bucle infinito.

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

int a[10005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int x;
    cin >> x;

    int lo = 0, hi = n - 1, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == x) { ans = mid; break; }
        else if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

Catorce comparaciones para buscar entre diez mil números; veinte para buscar entre un millón. Eso es lo que compra O(log n), y solo funciona porque los datos están ordenados: el orden es información, y la búsqueda binaria es cómo la gastas. En el mundo real, lower_bound de la biblioteca estándar de C++ es exactamente esto, y es el motor interno de los índices de bases de datos. El último problema, Suma máxima de subarray, plantea otra pregunta: no "dónde está" sino "cuál es el mejor tramo".

Análisis profundo

Por qué funciona

Dices 50, te dicen "más bajo" y la mitad de las posibilidades desaparece con una pregunta. La búsqueda binaria es ese movimiento, hecho exacto con índices.

El coste

O(log n): catorce comparaciones para diez mil números, veinte para un millón. Un recorrido lineal necesita un millón: cincuenta mil veces más trabajo.

Dónde falla

Escribir while (lo < hi) hace que un rango con exactamente un elemento nunca se examine, así que n = 1 siempre responde −1.
Escribir hi = mid en vez de hi = mid - 1 entra en bucle infinito con lo <= hi, y congela la pestaña.

Siguiente paso

El último problema cambia la pregunta: no "dónde está" sino "qué tramo es el mejor": Suma máxima de subarray.

Dos cosas para recordar

El orden es información; la búsqueda binaria es cómo la gastas.
La idea es fácil: los límites lo <= hi y mid ± 1 son donde se rompe.

🐞 Esta versión falla: ábrela y pruébala

lo < hi nunca examina un rango de un elemento: con n = 1 siempre responde −1

#include <iostream>
using namespace std;

int a[10005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int x;
    cin >> x;

    int lo = 0, hi = n - 1, ans = -1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == x) { ans = mid; break; }
        else if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    cout << ans << endl;
    return 0;
}