Búsqueda Binaria

La idea: dividir a la mitad

Imagina que juegas "adivina el número". Tu amigo piensa un número del 1 al 100 y tú solo puedes preguntar "¿es mayor o menor?". La estrategia más inteligente: siempre preguntar por la mitad.

• "¿Es 50?" → "Mayor"
• "¿Es 75?" → "Menor"
• "¿Es 62?" → "Mayor"
• "¿Es 68?" → "¡Sí!"

En solo 7 preguntas puedes encontrar cualquier número entre 1 y 100. Con búsqueda lineal (probar uno por uno), podrías necesitar hasta 100.

Búsqueda binaria funciona igual: en un arreglo ordenado, compara con el elemento del medio. Si es menor, busca en la mitad izquierda. Si es mayor, en la derecha. En cada paso, eliminamos la mitad del espacio de búsqueda.

Requisito fundamental

Implementación básica

int busquedaBinaria(vector<int> &v, int objetivo) {
    int lo = 0, hi = v.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // Punto medio

        if (v[mid] == objetivo) {
            return mid;      // ¡Encontrado!
        } else if (v[mid] < objetivo) {
            lo = mid + 1;    // Buscar en la mitad derecha
        } else {
            hi = mid - 1;    // Buscar en la mitad izquierda
        }
    }

    return -1;  // No encontrado
}

¿Por qué lo + (hi - lo) / 2 en lugar de (lo + hi) / 2? Para evitar overflow. Si lo y hi son muy grandes, su suma podría superar el rango de int.

Paso a paso

Buscar 7 en [1, 3, 5, 7, 9, 11, 13]:

Buscar 6:

Complejidad

• Tiempo: $O(\log n)$
• Espacio: $O(1)$

¡Con solo 30 comparaciones puedes buscar entre MIL MILLONES de elementos!

Funciones de búsqueda binaria en C++

C++ ya tiene búsqueda binaria incorporada:

vector<int> v = {1, 3, 5, 7, 9, 11};

// ¿Existe el elemento?
bool existe = binary_search(v.begin(), v.end(), 7);  // true

// Posición del primer elemento >= x
auto it = lower_bound(v.begin(), v.end(), 6);  // Apunta a 7 (índice 3)
int pos = it - v.begin();  // 3

// Posición del primer elemento > x
auto it2 = upper_bound(v.begin(), v.end(), 7);  // Apunta a 9 (índice 4)

Búsqueda binaria en la respuesta

Esta es una técnica poderosísima en competencias. En lugar de buscar un elemento en un arreglo, buscas la respuesta óptima a un problema.

Patrón: Si puedes formular la pregunta "¿es posible lograr una respuesta de X?", y la respuesta cambia de "No" a "Sí" (o viceversa) en algún punto, puedes hacer búsqueda binaria.

Ejemplo: cortar troncos

Problema: Tienes N troncos de diferentes longitudes. Necesitas obtener K troncos de longitud L cortándolos. ¿Cuál es la L máxima posible?

bool esPosible(vector<int> &troncos, int longitud, int k) {
    int total = 0;
    for (int t : troncos) {
        total += t / longitud;
    }
    return total >= k;
}

int maxLongitud(vector<int> &troncos, int k) {
    int lo = 1, hi = *max_element(troncos.begin(), troncos.end());
    int respuesta = 0;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (esPosible(troncos, mid, k)) {
            respuesta = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return respuesta;
}

Ejercicio de práctica

Dado un arreglo ordenado con posibles duplicados, encuentra cuántas veces aparece un número X.

Entrada:

8 3
1 2 3 3 3 4 5 6

Salida: 3

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];

    auto lo = lower_bound(v.begin(), v.end(), x);
    auto hi = upper_bound(v.begin(), v.end(), x);

    cout << (hi - lo) << endl;

    return 0;
}

Siguiente paso

Aprende sobre Lower y Upper Bound para dominar las variantes de búsqueda binaria.