Data Structure & Algorithms
Linear search, binary search, lower y upper bounds, condiciones monotónicas y búsqueda sobre un dominio de respuestas posibles.
Buscar consiste en reducir un espacio de candidatos hasta encontrar una respuesta o demostrar que no existe.
La clave no es memorizar mid. Es definir qué región todavía puede contener la respuesta.
function linearSearch<T>(
values: readonly T[],
target: T,
equals: (a: T, b: T) => boolean = Object.is,
): number {
for (let index = 0; index < values.length; index += 1) {
if (equals(values[index], target)) return index;
}
return -1;
}Sea n la cantidad de elementos:
O(1), el primero coincide;O(n) bajo una distribución razonable de posiciones;O(n), está al final o no existe;O(1).Linear search no es “malo”. Es óptimo cuando no existe estructura adicional que permita descartar candidatos. Para una búsqueda única en datos sin ordenar, ordenar primero costaría más.
La versión clásica necesita un array ordenado según el mismo comparador usado para buscar.
[1, 3, 5, 7, 9, 11]
↑ midSi target < values[mid], todos los elementos a la derecha pueden descartarse. Esa conclusión depende del orden.
Esta implementación mantiene un intervalo inclusivo [left, right].
type Comparator<T> = (a: T, b: T) => number;
function binarySearch<T>(
values: readonly T[],
target: T,
compare: Comparator<T>,
): number {
let left = 0;
let right = values.length - 1;
while (left <= right) {
const middle = left + Math.floor((right - left) / 2);
const order = compare(values[middle], target);
if (order === 0) return middle;
if (order < 0) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}Si target existe, está dentro de values[left..right] antes de cada iteración.
middle y todo lo anterior quedan descartados.middle y lo posterior.middle, así que el intervalo disminuye y el loop termina.Cada iteración reduce aproximadamente a la mitad el número de candidatos:
n → n/2 → n/4 → ... → 1La cantidad de pasos es O(log n). Espacio adicional: O(1) en la versión iterativa.
En lenguajes con enteros de tamaño fijo, (left + right) / 2 puede overflow. La fórmula:
left + floor((right - left) / 2)lo evita. En JavaScript, los índices de arrays reales no alcanzan el límite numérico de Number, pero la forma sigue siendo una buena convención transferible.
Otra plantilla usa [left, right), donde right está excluido.
function lowerBound<T>(
values: readonly T[],
target: T,
compare: Comparator<T>,
): number {
let left = 0;
let right = values.length;
while (left < right) {
const middle = left + Math.floor((right - left) / 2);
if (compare(values[middle], target) < 0) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
}lowerBound devuelve la primera posición donde el valor no es menor que target. Puede devolver values.length.
La búsqueda clásica puede devolver cualquier duplicado. Si necesitas límites:
lowerBound(target): primera posición >= target;upperBound(target): primera posición > target.La cantidad de ocurrencias es:
upperBound(target) - lowerBound(target)Esto evita expandirse linealmente desde una coincidencia.
Binary search puede trabajar sobre una función monotónica:
false false false false true true true
↑ primera truefunction firstTrue(
low: number,
high: number,
predicate: (value: number) => boolean,
): number | null {
let left = low;
let right = high;
let answer: number | null = null;
while (left <= right) {
const middle = left + Math.floor((right - left) / 2);
if (predicate(middle)) {
answer = middle;
right = middle - 1;
} else {
left = middle + 1;
}
}
return answer;
}Requisito:
Si
predicate(x)es verdadera, también debe ser verdadera para todos los valores posteriores dentro del dominio.
Sin monotonicidad, descartar un lado no es seguro.
Ejemplo: encontrar la capacidad mínima para enviar paquetes en days días.
El dominio no es un array de respuestas almacenadas. Es un rango de capacidades:
low = peso máximo individual
high = suma de todos los pesosLa condición canShip(capacity) es monotónica:
capacidad insuficiente → false
capacidad suficiente → true
más capacidad → sigue siendo truefunction minimumCapacity(weights: number[], days: number): number {
let low = Math.max(...weights);
let high = weights.reduce((sum, weight) => sum + weight, 0);
const canShip = (capacity: number): boolean => {
let usedDays = 1;
let load = 0;
for (const weight of weights) {
if (load + weight > capacity) {
usedDays += 1;
load = 0;
}
load += weight;
}
return usedDays <= days;
};
while (low < high) {
const middle = low + Math.floor((high - low) / 2);
if (canShip(middle)) {
high = middle;
} else {
low = middle + 1;
}
}
return low;
}Si evaluar la condición cuesta O(n) y el rango numérico tiene tamaño R, el tiempo es O(n log R), no O(log n).
Elegir low y high correctamente es parte del algoritmo.
En el ejemplo:
days >= 1.Un límite demasiado pequeño puede excluir la respuesta. Uno innecesariamente grande aumenta iteraciones y puede causar overflow en otros lenguajes.
Para una respuesta decimal no puedes esperar igualdad exacta. Repite una cantidad fija de iteraciones o hasta que el intervalo sea menor que una tolerancia.
for (let iteration = 0; iteration < 80; iteration += 1) {
const middle = (left + right) / 2;
// Keep the feasible half.
}La cantidad de iteraciones determina precisión. Debes considerar errores de punto flotante y qué lado del límite necesita el problema.
En un array ordenado rotado, al menos una mitad alrededor de middle permanece ordenada. Puedes identificarla y decidir si target cae dentro.
Con duplicados, distinguir la mitad ordenada puede volverse ambiguo y el peor caso puede degradarse a O(n).
Este ejemplo muestra que binary search se adapta cuando todavía puedes demostrar que una región no contiene la respuesta.
Encontrar el nodo medio cuesta O(n) porque no hay acceso por índice. Repetirlo produce un costo que puede acercarse a O(n log n) o requerir recorridos complejos. El orden por sí solo no basta; también importa la representación.
Prueba especialmente:
false;true;[left, right] con [left, right).left = middle y no reducir el intervalo.O(log n) cuando el predicate cuesta O(n).¿Por qué binary search on answer puede funcionar aunque la respuesta no aparezca en ninguna colección?
Porque busca en un dominio ordenado de candidatos y usa una condición monotónica para descartar regiones. Los candidatos pueden ser números posibles, no elementos almacenados.