Búsqueda binaria y sus variantes

Buscar en un arreglo ordenado mirando el elemento del medio y descartando la mitad es de los primeros algoritmos que se aprenden. También es uno de los que más se escribe con errores: el $\pm 1$ mal puesto, el ciclo que no termina, el resultado correcto en un ejemplo y equivocado en el borde.

De dónde sale el logaritmo

Cada paso deja la mitad del espacio de búsqueda, así que después de $k$ pasos quedan $n/2^k$ candidatos. Con un candidato alcanza, y de ahí sale el costo: $\Theta(\log n)$.

La escala es difícil de intuir. En un millón de elementos son 20 pasos; en mil millones, 30. Duplicar los datos agrega un solo paso. El precio es la precondición: el arreglo tiene que estar ordenado y permitir acceso por índice en tiempo constante.

Escribir la invariante antes que el código

La forma de no equivocarse es escribir la invariante antes que el código. Con el intervalo semiabierto $[bajo, alto)$, la invariante es que la respuesta, si existe, está adentro.

El medio se calcula como bajo + (alto - bajo) / 2, no como (bajo + alto) / 2: la segunda puede desbordar el entero con arreglos grandes, y ese bug estuvo años en bibliotecas estándar. Si el medio no sirve, se avanza bajo = medio + 1 o se recorta alto = medio. El ciclo termina cuando el intervalo queda vacío, y cada paso lo achica: por eso no se cuelga.

Con repetidos, encontrarlo deja de ser una respuesta

Con elementos repetidos, “encontrarlo” deja de ser una sola respuesta. Las dos variantes útiles son el primer índice cuyo valor es mayor o igual al buscado, y el primero estrictamente mayor.

La segunda menos la primera da cuántas veces aparece el valor, y juntas delimitan el rango de los iguales. Estas versiones no cortan al encontrar una coincidencia: siguen hasta agotar el intervalo, porque buscan un borde, no un elemento.

Olvidarse del arreglo: buscar sobre un predicado

La generalización que más rinde es olvidarse del arreglo. Si hay un predicado monótono —falso hasta cierto punto y verdadero de ahí en adelante—, la búsqueda binaria encuentra ese punto de cambio. Lo único que hace falta es la monotonía, no los datos.

Eso permite buscar sobre la respuesta: la capacidad mínima que alcanza para repartir la carga, la velocidad mínima que permite terminar a tiempo. Se define “¿con este valor se puede?”, se verifica que sea monótona y se binariza sobre el rango de valores posibles.

Sobre reales, el corte es por tolerancia

Sobre números reales la mecánica es la misma con un cambio: no hay intervalo vacío al que llegar. El corte se hace por tolerancia —cuando el intervalo es más chico que un $\varepsilon$— o, más robusto, por una cantidad fija de iteraciones: cien pasos dejan el intervalo dividido por $2^{100}$, muy por debajo de la precisión del punto flotante.

Es la misma idea que el método de bisección para encontrar raíces.

Dos casos donde no conviene

Hay dos casos donde no conviene. Sobre una lista enlazada no hay acceso por índice, así que llegar al medio ya cuesta lineal y se pierde la ventaja.

Y sobre datos que cambian todo el tiempo, mantener el arreglo ordenado en cada inserción cuesta más que las búsquedas que ahorra: ahí van un árbol balanceado o una tabla hash, según haga falta el orden o no.

Escribirla sin equivocarse

La versión que devuelve la posición del valor, o −1 si no está:

const binarySearch = (values: readonly number[], target: number): number => {
  let low = 0;
  let high = values.length - 1; // inclusivo: el rango vivo es [low, high]

  while (low <= high) {
    const middle = low + Math.floor((high - low) / 2);
    const current = values[middle]!;

    if (current === target) return middle;
    if (current < target) low = middle + 1;
    else high = middle - 1;
  }

  return -1;
};

Hay tres decisiones acá y las tres son donde se rompe. La primera es que high empieza en length - 1 y el rango es cerrado de los dos lados: por eso la condición es low <= high y no low < high. Si el rango fuera [low, high), las tres líneas cambiarían de forma coherente, y mezclar las dos convenciones es el origen de la mitad de los errores.

La segunda es low + (high - low) / 2 en vez de (low + high) / 2. En un lenguaje con enteros de tamaño fijo, la suma puede desbordar con arreglos grandes; la resta no puede. El error estuvo veinte años en la implementación de la biblioteca estándar de Java antes de que alguien lo encontrara.

La tercera es que los dos lados avanzan: middle + 1 y middle - 1. Si alguno se quedara en middle, el rango dejaría de achicarse cuando le queden dos elementos y el ciclo no terminaría.

Cuándo conviene de verdad

La regla práctica sale de ahí: la búsqueda binaria conviene cuando los datos ya están ordenados por otro motivo, o cuando se va a buscar muchas veces sobre datos que casi no cambian. Si hay que ordenar sólo para poder buscar una vez, el ordenamiento cuesta más que la búsqueda lineal que se estaba tratando de evitar.

Cierre

Búsqueda binaria es una invariante bien escrita más un predicado monótono. Con el intervalo semiabierto y el medio calculado sin desbordar, sale la versión exacta, las de borde con repetidos y la búsqueda sobre la respuesta, que es donde deja de ser un truco de arreglos ordenados.