Binary search#

Metadatos

Tipo: Algoritmo · Nivel: Principiante · Dificultad: 1.5 · Complejidad: O(log n)

Requisitos: Bucles

Busca un valor en un array ordenado dividiendo el espacio de búsqueda por la mitad en cada paso. Devuelve la posición del valor, o -1 si no está.

Buscamos 9: como el central (7) es menor, el objetivo solo puede estar a la derecha, así que descartamos de golpe la mitad izquierda.

Idea#

Al estar el array ordenado, comparar el objetivo con el elemento central nos dice en qué mitad puede estar: si el central es menor que el objetivo, este solo puede estar a la derecha; si es mayor, solo a la izquierda. Cada comparación descarta, por tanto, la mitad de los candidatos que quedaban.

El bucle mantiene una invariante muy simple: si target está en el array, siempre se encuentra dentro del rango [lo, hi]. Al principio ese rango es [0, n-1] y cubre todo el array; cada iteración lo reduce a la mitad sin perder nunca el objetivo, hasta encontrarlo o hasta que el rango queda vacío (lo > hi), señal inequívoca de que no está.

Código#

C++Python

fullcleancontest

/**
 * Binary search on a sorted vector.
 *
 * Finds a value in a sorted array by halving the search range at each step,
 * turning an O(n) scan into O(log n).
 *
 * Input:  a — vector sorted in non-decreasing order; target — value to find.
 * Output: an index i with a[i] == target, or -1 if target is not present.
 * Complexity: O(log n) time, O(1) space.
 */
#include <vector>
using namespace std;

int binary_search_idx(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;    // search the closed range [lo, hi]
    // Invariant: if target is in the array, it always lies within [lo, hi].
    while (lo <= hi) {                      // stop only when the range is empty
        int mid = lo + (hi - lo) / 2;       // same as (lo+hi)/2, but never overflows int
        if (a[mid] == target) return mid;   // found it
        if (a[mid] < target) lo = mid + 1;  // target is to the right; discard mid and left
        else                 hi = mid - 1;  // target is to the left; discard mid and right
    }
    return -1;                              // range emptied: target is not present
}

#include <vector>
using namespace std;

int binary_search_idx(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else                 hi = mid - 1;
    }
    return -1;
}

#include <vector>
using namespace std;
int binary_search_idx(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else                 hi = mid - 1;
    }
    return -1;
}

fullcleancontest

"""Binary search on a sorted list.

Finds a value in a **sorted** array by halving the search range at each step,
turning an O(n) scan into O(log n).

Args:
    a (list[int]): array sorted in non-decreasing order.
    target (int): value to look for.
Returns:
    int: an index ``i`` with ``a[i] == target``, or ``-1`` if it is not present.

Complexity: O(log n) time, O(1) space.
"""


def binary_search(a: list[int], target: int) -> int:
    lo: int = 0
    hi: int = len(a) - 1          # search the closed range [lo, hi]
    # Invariant: if target is in the array, it always lies within [lo, hi].
    while lo <= hi:               # stop only when the range is empty
        mid: int = (lo + hi) // 2  # Python ints never overflow, so this is safe
        if a[mid] == target:
            return mid            # found it
        if a[mid] < target:
            lo = mid + 1          # target is to the right; discard mid and left
        else:
            hi = mid - 1          # target is to the left; discard mid and right
    return -1                     # range emptied: target is not present

def binary_search(a: list[int], target: int) -> int:
    lo: int = 0
    hi: int = len(a) - 1
    while lo <= hi:
        mid: int = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

def binary_search(b, f):
    d = 0
    c = len(b) - 1
    while d <= c:
        e = (d + c) // 2
        if b[e] == f:
            return e
        if b[e] < f:
            d = e + 1
        else:
            c = e - 1
    return -1

Precondición

El array debe estar ordenado. Si no lo está, ordénalo primero (O(n log n)).

Cómo funciona#

Sigamos la traza sobre 1 3 5 7 9 11 buscando el 7:

`lo`	`hi`	`mid`	`a[mid]`	Comparación	Acción
0	5	2	5	`5 < 7`	`lo = mid + 1 = 3`
3	5	4	9	`9 > 7`	`hi = mid - 1 = 3`
3	3	3	7	`7 == 7`	devuelve `3`

Con 6 elementos hemos necesitado solo 3 comparaciones. Dos detalles de la implementación merecen atención:

mid = lo + (hi - lo) / 2 evita el desbordamiento. Da el mismo índice que (lo + hi) / 2, pero esta última puede desbordar el rango de int si lo + hi supera el máximo representable (con arrays muy grandes). Restar primero elimina esa suma peligrosa. En Python los enteros no desbordan, así que allí (lo + hi) // 2 es igual de seguro.
Disciplina de los +1 / -1. Cuando a[mid] < target ya sabemos que mid no es la respuesta, así que lo descartamos con lo = mid + 1; de forma simétrica, hi = mid - 1 cuando a[mid] > target. Si escribiéramos lo = mid o hi = mid, el rango podría dejar de encogerse y el bucle entraría en un ciclo infinito.

Complejidad#

Cada iteración descarta la mitad de los elementos, de modo que hacemos a lo sumo ⌈log₂ n⌉ comparaciones: de ahí el coste O(log n). Solo usamos un par de índices, por lo que la memoria es O(1).

Operación	Complejidad
Búsqueda	O(log n)
Memoria	O(1)

Ejemplos#

Array	Buscar	Resultado
`1 3 5 7 9 11`	`7`	`3` (posición)
`1 3 5 7 9 11`	`4`	`-1` (no está)

Búsqueda binaria sobre la respuesta#

Una técnica muy habitual en concursos es la búsqueda binaria sobre la respuesta: en vez de buscar un valor dentro de un array, buscamos el menor (o mayor) valor x que cumple una condición monótona —una que, una vez se vuelve cierta, sigue siéndolo para valores mayores—. La mecánica es idéntica: si sabemos comprobar rápido «¿basta con x?», hacemos búsqueda binaria sobre el rango de respuestas posibles y bastan O(log(rango)) comprobaciones. Aparece en problemas del tipo «minimiza la capacidad máxima» o «¿cabe todo en k grupos?».

Cuándo NO usarlo#

Una sola búsqueda en un array desordenado: ordenarlo cuesta O(n log n); si solo vas a buscar una vez, un recorrido lineal O(n) es más simple y rápido.
Datos que cambian mucho (inserciones/borrados frecuentes): mantener el array ordenado es caro. Un conjunto hash (unordered_set en C++, set en Python) responde a "¿está?" en O(1) medio sin reordenar nada.
Para buscar el primero ≥ x o contar repetidos, usa las variantes lower_bound / upper_bound: siguen siendo búsqueda binaria, pero te evitan reescribir el bucle.

Errores comunes#

Olvidar que el array debe estar ordenado: sin orden, a[mid] no dice nada sobre en qué mitad seguir buscando.
Usar < en lugar de <= en la condición del bucle: se saltaría el último caso, cuando el rango se reduce a un único elemento (lo == hi).
Escribir lo = mid o hi = mid en vez de mid ± 1, lo que provoca un bucle infinito.
Calcular mid como (lo + hi) / 2 en lenguajes con enteros de tamaño fijo: riesgo de desbordamiento con índices grandes.

Referencias#

CP-Algorithms: Binary search