¿Recuerdas las Páginas Amarillas?
Ese libro gordo lleno de números de teléfono organizados alfabéticamente. Si querías encontrar el número de alguien, no empezabas desde la primera página leyendo uno por uno (¡te llevaría horas!).
En lugar de eso, ibas directo al medio, revisabas, y decidías si avanzar o retroceder en el libro. Esa es la idea de Binary Search.

Es un algoritmo para buscar un elemento en una lista ordenada dividiéndola a la mitad en cada paso.
En lugar de revisar uno por uno, Binary Search va directo al punto, descartando la mitad de los datos cada vez.

1. Coloca dos marcadores: inicio y fin.
2. Calcula el punto medio.
3. Si el elemento buscado está en el medio → ¡Encontrado!
4. Si es menor que el medio → busca en la mitad izquierda.
5. Si es mayor que el medio → busca en la mitad derecha.
6. Repite hasta encontrarlo o hasta que inicio > fin.

Tienes un arreglo ordenado con los IDs de tesoros enterrados en una isla:

[3, 7, 14, 21, 28, 35, 42, 50]

Y tu misión es encontrar el tesoro con ID 28.

graph LR
    A1[3]:::normal --> A2[7]:::normal --> A3[14]:::normal --> A4[21]:::medio --> A5[28]:::normal --> A6[35]:::normal --> A7[42]:::normal --> A8[50]:::normal
    classDef medio fill:#FFD700,stroke:#333,stroke-width:2px;
    classDef normal fill:#B6FFB6,stroke:#333,stroke-width:1px;

    B1[XX]:::descartado --> B2[XX]:::descartado --> B3[XX]:::descartado --> B4[XX]:::descartado --> B5[28]:::normal --> B6[35]:::medio --> B7[42]:::normal --> B8[50]:::normal
    classDef medio fill:#FFD700,stroke:#333,stroke-width:2px;
    classDef normal fill:#B6FFB6,stroke:#333,stroke-width:1px;
    classDef descartado fill:#FFB6B6,stroke:#333,stroke-width:1px;

    C1[XX]:::descartado --> C2[XX]:::descartado --> C3[XX]:::descartado --> C4[XX]:::descartado --> C5[28]:::encontrado --> C6[XX]:::descartado --> C7[XX]:::descartado --> C8[XX]:::descartado
    classDef encontrado fill:#90EE90,stroke:#333,stroke-width:2px;
    classDef descartado fill:#FFB6B6,stroke:#333,stroke-width:1px;

• Tenemos el array ordenado: [3, 7, 14, 21, 28, 35, 42, 50].
• Los punteros Inicio y Fin están en los índices 0 y 7 respectivamente (todo el array).
• Calculamos el índice Medio como (0 + 7) / 2 = 3.
• El valor en el medio es 21.
• Comparamos el valor buscado 28 con 21.
• Como 28 es mayor que 21, descartamos toda la mitad izquierda (desde el índice 0 hasta 3).
• Actualizamos Inicio al índice 4 para el siguiente paso.

• Ahora el rango de búsqueda es desde índice 4 hasta índice 7.
• El subarray considerado es [28, 35, 42, 50].
• Calculamos el nuevo índice Medio: (4 + 7) / 2 = 5.
• El valor en el medio es 35.
• Comparamos 28 con 35.
• Como 28 es menor que 35, descartamos toda la mitad derecha (índices mayores a 5).
• Actualizamos Fin al índice 4 para el siguiente paso.

• El rango se ha reducido al índice 4 solamente.
• El índice Inicio, Fin y Medio coinciden en 4.
• El valor en esa posición es 28, que es el número que estamos buscando.
• La búsqueda termina con éxito.

Para aplicar binary search con éxito, la condición debe ser monótona, es decir, debe dividir el espacio de búsqueda en una parte falsa seguida de una parte verdadera (o viceversa), con un único punto donde cambia.

Ejemplo: Queremos encontrar el primer índice donde el valor sea mayor o igual a 28 en la siguiente lista:

🔍 Observa:

• La condición es Falsa (❌) hasta el índice 3
• Desde el índice 4 en adelante es Verdadera (✅)
• La búsqueda binaria encuentra el índice 4, donde comienza la verdad.

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

int binarySearch(const vector<int>& arr, int target) {
    int inicio = 0;
    int fin = arr.size() - 1;

    while (inicio <= fin) {
        int medio = inicio + (fin - inicio) / 2; // evita overflow
        if (arr[medio] == target) {
            return medio; // encontrado
        }
        if (arr[medio] < target) {
            inicio = medio + 1; // buscar derecha
        } else {
            fin = medio - 1; // buscar izquierda
        }
    }
    return -1; // no encontrado
}

int main() {
    vector<int> tesoros = {3, 7, 14, 21, 28, 35, 42, 50};
    int buscar = 28;
    int resultado = binarySearch(tesoros, buscar);

    if (resultado != -1)
        cout << "Tesoro encontrado en la posición " << resultado << endl;
    else
        cout << "Tesoro no encontrado" << endl;

    return 0;
}

• Orden obligatorio: Binary Search solo funciona si el arreglo está ordenado.
• Complejidad:
  • Mejor caso: O(1) → si el elemento está justo en el medio.
  • Peor caso: O(log n) → ¡muy rápido incluso con millones de datos!
• Evita overflow al calcular medio usando:

  int medio = inicio + (fin - inicio) / 2;

Prueba el código cambiando:

• El valor de buscar.
• El tamaño del vector.
• Qué pasa si el valor no existe.

¡Y recuerda! Binary Search es exactamente lo que hacías con las Páginas Amarillas: una mezcla de intuición y dividir para conquistar. 📚🔍

Qué hace: Busca un elemento exacto en un arreglo ordenado.
Cuándo usar: Cuando tienes un arreglo ordenado y quieres encontrar la posición de un valor.

#include <vector>
using namespace std;

int binary_search(const vector<int>& arr, int x) {
    int left = 0, right = (int)arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) return mid;
        else if (arr[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // No encontrado
}

Qué hace: Encuentra el primer índice donde el elemento es ≥ x.
Cuándo usar: Para insertar un valor en orden o contar cuántos elementos son menores que x.

int lower_bound(const vector<int>& arr, int x) {
    int left = 0, right = (int)arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < x) left = mid + 1;
        else right = mid;
    }
    return left;
}

Qué hace: Encuentra el primer índice donde el elemento es > x.
Cuándo usar: Para contar cuántos elementos son ≤ x.

int upper_bound(const vector<int>& arr, int x) {
    int left = 0, right = (int)arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= x) left = mid + 1;
        else right = mid;
    }
    return left;
}

Qué hace: Busca el primer índice donde una condición monótona pasa a ser verdadera.
Cuándo usar: Cuando la condición depende del índice y cambia de falso a verdadero una sola vez.

// bool condition(int i); // condición definida externamente

int first_true(int low, int high) {
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (condition(mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}

Qué hace: Busca el mínimo valor que cumple una condición monótona (no tiene que ser índice).
Cuándo usar: Cuando la respuesta es un valor (entero o real) y necesitas encontrar el óptimo.

// bool condition(int x); // condición definida externamente

int binary_search_answer(int low, int high) {
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (condition(mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}

Qué hace: Busca un elemento en arreglo ordenado pero rotado.
Cuándo usar: Cuando el arreglo está desplazado en algún punto, pero sigue ordenado cíclicamente.

int find_rotation_point(const vector<int>& arr) {
    int left = 0, right = (int)arr.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] > arr[right]) left = mid + 1;
        else right = mid;
    }
    return left;
}

int rotated_binary_search(const vector<int>& arr, int x) {
    int rot = find_rotation_point(arr);
    int left, right;
    if (x >= arr[rot] && x <= arr.back()) {
        left = rot; right = (int)arr.size() - 1;
    } else {
        left = 0; right = rot - 1;
    }
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) return mid;
        else if (arr[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Qué hace: Busca un valor real aproximado que cumple una condición con precisión.
Cuándo usar: Cuando la respuesta es continua y necesitas aproximar (raíz cuadrada, optimización, etc).

double sqrt_approx(double n, double precision = 1e-6) {
    double low = 0, high = n > 1 ? n : 1;
    while (high - low > precision) {
        double mid = (low + high) / 2;
        if (mid * mid < n) low = mid;
        else high = mid;
    }
    return (low + high) / 2;
}

Qué hace: Encuentra el máximo o mínimo de una función unimodal dividiendo el rango en tres.
Cuándo usar: Cuando la función tiene un solo máximo o mínimo (unimodal).

// double f(double x); // función unimodal definida externamente

double ternary_search(double low, double hig, int iterations = 100) {
    for (int i = 0; i < iterations; i++) {
        double m1 = low + (high - low) / 3;
        double m2 = high - (high - low) / 3;
        if (f(m1) < f(m2)) low = m1;
        else high = m2;
    }
    return (low + high) / 2;
}

1. 702C - Cellular Network
2. 706B - Interesting drink
3. 812C - Sagheer and Nubian Market
4. 1197C - Array Splitting
5. 1486B - Eastern Exhibition
6. 189A - Cut Ribbon
7. 977C - Less or Equal
8. 1076C - Meme Problem

1. E. Broken Keyboard - Codeforces Round #451 Div. 2
2. B. Binary Search - Codeforces Round #269 Div. 2
3. D. Gears - Codeforces Round #257 Div. 2

4. Typical90 - Problem 024: Binary Search (C++ template)
5. ABC185-D: Stamp - AtCoder Beginner Contest 185
6. AGC007-B: Triple - AtCoder Grand Contest 007

7. CSES Problem Set - Elevator Rides
8. CSES Problem Set - Minimize Max Distance
9. CSES Problem Set - Factory Machines

10. 704. Binary Search
11. 34. Find First and Last Position of Element in Sorted Array
12. 668. Kth Smallest Number in Multiplication Table
13. 2187. Minimum Time to Complete Trips

14. AGGRCOW - Aggressive cows
15. KQUERY - K-query