Casi todo el mundo sabe escribir búsqueda binaria sobre un arreglo ordenado. Casi nadie recurre a ella cuando el problema nunca menciona un arreglo.
De esa brecha trata esta parte. Cuatro de los cinco patrones de aquí no buscan en ninguna colección.
Cada programa de abajo está completo, se ejecutó en .NET 10, y su salida está pegada de la ejecución.
Patrón 16 — Lo que Array.BinarySearch te da, y lo que no
La BCL ya la trae, y su valor de retorno cuando no encuentra nada es la característica más desaprovechada de toda la clase.
int[] a = [10, 20, 20, 20, 30, 40];
// The BCL search. On a miss it returns the bitwise complement of where the
// value WOULD go — which is the insertion point, not an error.
foreach (int want in new[] { 30, 25, 5, 50 })
{
int r = Array.BinarySearch(a, want);
Console.WriteLine(r >= 0
? $"BinarySearch({want,2}) = {r,2} found at index {r}"
: $"BinarySearch({want,2}) = {r,2} not found; ~{r} = {~r} is where it would go");
}
// With duplicates, BinarySearch promises nothing about WHICH match you get.
// These two do.
static int LowerBound(int[] a, int x) // first index with a[i] >= x
{
int lo = 0, hi = a.Length;
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
if (a[mid] < x) lo = mid + 1; else hi = mid;
}
return lo;
}
static int UpperBound(int[] a, int x) // first index with a[i] > x
{
int lo = 0, hi = a.Length;
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
if (a[mid] <= x) lo = mid + 1; else hi = mid;
}
return lo;
}
Console.WriteLine();
Console.WriteLine($"a = [{string.Join(", ", a)}]");
foreach (int x in new[] { 20, 25 })
{
int lb = LowerBound(a, x), ub = UpperBound(a, x);
Console.WriteLine($"x={x,2} lower={lb} upper={ub} count={ub - lb}");
}Imprime:
BinarySearch(30) = 4 found at index 4
BinarySearch(25) = -5 not found; ~-5 = 4 is where it would go
BinarySearch( 5) = -1 not found; ~-1 = 0 is where it would go
BinarySearch(50) = -7 not found; ~-7 = 6 is where it would go
a = [10, 20, 20, 20, 30, 40]
x=20 lower=1 upper=4 count=3
x=25 lower=4 upper=4 count=0Un resultado negativo no es un código de error. Es ~insertionPoint: el complemento a nivel de bits de dónde iría el valor. ~(-5) es 4, así que 25 va en el índice 4. Esa sola línea reemplaza una segunda búsqueda en muchísimos problemas.
Lo que Array.BinarySearch no hace es decirte cuál de los duplicados encontraste. Con tres copias de 20 en el arreglo, la documentación solo promete que obtienes una de ellas. Por eso vale la pena tener las dos cotas escritas a mano, y el par responde más preguntas que cualquiera de las dos por separado.
lower es el primer índice no menor que x; upper es el primer índice mayor que x. Su separación es cuántas copias existen, y cuando coinciden el valor no está — que es también exactamente donde se insertaría.
Fíjate que ambas usan while (lo < hi) con hi empezando en a.Length, no en a.Length - 1. Es deliberado: la respuesta puede ser legítimamente «pasado el final», que es lo que ocurre con 50.
Costo: O(log n).
Úsalo cuando necesites un conteo de valores iguales, un punto de inserción, o el primer elemento al menos tan grande como cierta cota. upper - lower es el conteo, y no hace falta un recorrido aparte.
Patrón 17 — Búsqueda binaria sobre la respuesta
Este es el que importa.
Los paquetes deben enviarse en orden, a lo largo de D días. Elige la capacidad diaria más pequeña que entregue todo a tiempo.
No hay ningún arreglo que buscar. Pero mira la forma de la pregunta. Si la capacidad 20 funciona, entonces 21 funciona, y 22, y todo lo que esté por encima. Si 14 falla, 13 falla, y todo lo que esté por debajo. Así que las respuestas, puestas en orden, se ven así:
capacity: 10 11 12 13 14 15 16 17 18 19 20
works? F F F F F T T T T T TEso cambia exactamente una vez, y encontrar dónde algo cambia exactamente una vez es lo que la búsqueda binaria es. El arreglo ordenado nunca fue el requisito: era una forma de conseguir esta propiedad.
La búsqueda binaria no necesita un arreglo ordenado. Necesita una pregunta cuya respuesta cambie exactamente una vez. Aquí el arreglo nunca se construye — el predicado se evalúa bajo demanda, y la búsqueda persigue la frontera entre la última F y la primera T.
int[] weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
int days = 5;
// Can every package be shipped within `days` at this capacity? Packages must
// go in order, so this is a simple greedy pass.
static bool Feasible(int[] w, int days, int cap)
{
int used = 1, load = 0;
foreach (int x in w)
{
if (x > cap) return false;
if (load + x > cap) { used++; load = 0; }
load += x;
}
return used <= days;
}
int lo = weights.Max(); // cannot be less than the heaviest single item
int hi = weights.Sum(); // one day is always enough
Console.WriteLine($"searching capacities {lo}..{hi}\n");
while (lo < hi)
{
int mid = lo + (hi - lo) / 2;
bool ok = Feasible(weights, days, mid);
Console.WriteLine($"lo={lo,2} hi={hi,2} try {mid,2} -> {(ok ? "fits, so nothing bigger is needed: hi = mid" : "too small: lo = mid + 1")}");
if (ok) hi = mid; else lo = mid + 1;
}
Console.WriteLine($"\nsmallest capacity that works: {lo}");
Console.WriteLine($"check {lo}: {Feasible(weights, days, lo)} check {lo - 1}: {Feasible(weights, days, lo - 1)}");Imprime:
searching capacities 10..55
lo=10 hi=55 try 32 -> fits, so nothing bigger is needed: hi = mid
lo=10 hi=32 try 21 -> fits, so nothing bigger is needed: hi = mid
lo=10 hi=21 try 15 -> fits, so nothing bigger is needed: hi = mid
lo=10 hi=15 try 12 -> too small: lo = mid + 1
lo=13 hi=15 try 14 -> too small: lo = mid + 1
smallest capacity that works: 15
check 15: True check 14: FalseTres cosas hacen que esto funcione, y son la lista de comprobación para todo problema de esta forma:
- Una prueba de factibilidad.
Feasibleresponde sí o no para un candidato. Es un recorrido voraz sencillo, y se le permite ser algo lento: se ejecuta solo O(log rango) veces. - Monotonía. Una vez verdadero, siempre verdadero hacia arriba. Si eso falla, todo el enfoque es inválido, y es lo que hay que comprobar antes de escribir una sola línea de código.
- Cotas obviamente correctas.
loes el paquete más pesado, porque nada más pequeño puede enviarlo nunca.hies el total, porque eso siempre termina en un día. Ninguna necesita ser ajustada, solo correcta.
Las dos últimas líneas impresas son el hábito que vale la pena conservar: comprueba que la respuesta funciona y que la de justo abajo no. Detecta un error por uno de inmediato.
Costo: O(factibilidad × log rango).
Úsalo cuando el problema diga minimizar el máximo, maximizar el mínimo, o el menor X tal que. Esa redacción es casi una garantía.
Patrón 18 — El arreglo rotado
Un arreglo ordenado, rotado en un punto desconocido. Encuentra un objetivo en O(log n).
El instinto es encontrar primero el punto de rotación y después buscar. Eso funciona, y son dos búsquedas. Esta es una.
En cualquier división, el corte de la rotación solo puede caer en una mitad: solo hay un corte. Así que la otra mitad está bien ordenada, y puedes razonar sobre ella con normalidad.
La comparación a[lo] ≤ a[mid] es todo el truco. No prueba el objetivo — identifica sobre qué mitad puedes razonar con normalidad.
int[] a = [4, 5, 6, 7, 0, 1, 2];
static int Search(int[] a, int target)
{
int lo = 0, hi = a.Length - 1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
// Exactly one half is guaranteed to be sorted. Find it, then ask
// whether the target lies inside it.
if (a[lo] <= a[mid])
{
Console.WriteLine($" lo={lo} mid={mid} hi={hi} left half [{a[lo]}..{a[mid]}] is sorted");
if (a[lo] <= target && target < a[mid]) hi = mid - 1; else lo = mid + 1;
}
else
{
Console.WriteLine($" lo={lo} mid={mid} hi={hi} right half [{a[mid]}..{a[hi]}] is sorted");
if (a[mid] < target && target <= a[hi]) lo = mid + 1; else hi = mid - 1;
}
}
return -1;
}
Console.WriteLine($"a = [{string.Join(", ", a)}]\n");
foreach (int t in new[] { 0, 6, 3 })
{
Console.WriteLine($"target {t}:");
Console.WriteLine($" -> {Search(a, t)}\n");
}Imprime:
a = [4, 5, 6, 7, 0, 1, 2]
target 0:
lo=0 mid=3 hi=6 left half [4..7] is sorted
lo=4 mid=5 hi=6 left half [0..1] is sorted
-> 4
target 6:
lo=0 mid=3 hi=6 left half [4..7] is sorted
lo=0 mid=1 hi=2 left half [4..5] is sorted
-> 2
target 3:
lo=0 mid=3 hi=6 left half [4..7] is sorted
lo=4 mid=5 hi=6 left half [0..1] is sorted
lo=6 mid=6 hi=6 left half [2..2] is sorted
-> -1La comparación a[lo] <= a[mid] no tiene nada que ver con el objetivo. Pregunta qué mitad está intacta. Solo después se prueba el objetivo, contra el rango conocido de esa mitad.
Mira la ejecución de target 3: nunca encuentra nada, y aun así reduce a la mitad la búsqueda en cada paso, terminando en tres comparaciones en lugar de siete.
Costo: O(log n).
Úsalo cuando los datos estén ordenados pero desplazados: arreglos rotados, búferes circulares, un archivo de log que dio la vuelta.
Patrón 19 — Búsqueda binaria sobre números reales
Misma idea, dominio continuo. No hay un valor «siguiente» al que avanzar, así que el bucle no puede terminar con lo == hi.
La solución equivocada es while (hi - lo > 1e-9). Cerca de los límites de la precisión de un double, (lo + hi) / 2 puede quedar exactamente igual a lo, el intervalo deja de encogerse, y el bucle nunca termina. Pasa todas las pruebas que escribas y se cuelga en el juez.
La solución correcta es dejar de contar precisión y contar iteraciones.
// A FIXED iteration count, not an epsilon. 100 halvings takes any starting
// interval below 2^-100, which is far under what a double can represent — so
// this cannot spin forever, and it needs no tolerance argument.
static double Root(double x)
{
double lo = 0, hi = Math.Max(1.0, x);
for (int it = 0; it < 100; it++)
{
double mid = (lo + hi) / 2;
if (mid * mid < x) lo = mid; else hi = mid;
}
return lo;
}
foreach (double x in new[] { 2.0, 10.0, 0.25, 1e6 })
Console.WriteLine($"root({x,9}) = {Root(x):F10} Math.Sqrt = {Math.Sqrt(x):F10}");
Console.WriteLine();
Console.WriteLine($"{"iterations",11} {"interval width",18}");
double w = 1.0;
foreach (int n in new[] { 10, 30, 50, 100 })
{
w = Math.Pow(2, -n);
Console.WriteLine($"{n,11} {w,18:E3}");
}Imprime:
root( 2) = 1.4142135624 Math.Sqrt = 1.4142135624
root( 10) = 3.1622776602 Math.Sqrt = 3.1622776602
root( 0.25) = 0.5000000000 Math.Sqrt = 0.5000000000
root( 1000000) = 1000.0000000000 Math.Sqrt = 1000.0000000000
iterations interval width
10 9.766E-004
30 9.313E-010
50 8.882E-016
100 7.889E-031Cien divisiones a la mitad reducen cualquier intervalo inicial por un factor de 2⁻¹⁰⁰, que es alrededor de 7.9 × 10⁻³¹, muy por debajo de lo que un double puede representar. Así que cien iteraciones son siempre suficientes, no cuestan nada, y no pueden ciclar para siempre. Cincuenta suele bastar. Usa cien y deja de pensar en ello.
Costo: O(iteraciones), una constante fija.
Úsalo cuando la respuesta sea un número real: una tasa, una razón, una distancia, un tiempo.
Patrón 20 — Búsqueda ternaria, cuando la respuesta no es monótona
La búsqueda binaria necesita que la respuesta sí/no cambie una vez. Algunos problemas no te dan eso. Una función que baja y luego sube no tiene punto de cambio: tiene un mínimo, y a ambos lados de él la función va en la dirección equivocada.
Un solo sondeo no puede decirte de qué lado del mínimo estás. Dos sí.
La búsqueda binaria necesita que la respuesta a una pregunta sí/no cambie una vez. La búsqueda ternaria necesita menos: solo que la función baje y luego suba. Dos sondeos te dicen qué tercio exterior no puede contener el mínimo.
// Unimodal: falls, then rises. Binary search needs monotonic, which this is
// not — but the minimum can still be bracketed, by comparing two interior
// points instead of one.
static double F(double x) => (x - 2.5) * (x - 2.5) + 1;
double lo = 0, hi = 10;
for (int it = 0; it < 200; it++)
{
double m1 = lo + (hi - lo) / 3;
double m2 = hi - (hi - lo) / 3;
if (F(m1) < F(m2)) hi = m2; else lo = m1;
if (it < 4)
Console.WriteLine($"it={it} m1={m1:F4} f={F(m1):F4} m2={m2:F4} f={F(m2):F4} -> [{lo:F4}, {hi:F4}]");
}
double x = (lo + hi) / 2;
Console.WriteLine($"\nminimum at x = {x:F8}, f(x) = {F(x):F8}");Imprime:
it=0 m1=3.3333 f=1.6944 m2=6.6667 f=18.3611 -> [0.0000, 6.6667]
it=1 m1=2.2222 f=1.0772 m2=4.4444 f=4.7809 -> [0.0000, 4.4444]
it=2 m1=1.4815 f=2.0374 m2=2.9630 f=1.2143 -> [1.4815, 4.4444]
it=3 m1=2.4691 f=1.0010 m2=3.4568 f=1.9154 -> [1.4815, 3.4568]
minimum at x = 2.50000001, f(x) = 1.00000000Ahora mira de cerca esa respuesta: x = 2.50000001, pero f(x) = 1.00000000.
El valor de la función es correcto hasta dieciséis dígitos, mientras que la ubicación solo lo es hasta ocho. Eso no es un error del bucle, y más iteraciones no lo arreglarán. Cerca de un mínimo una función suave es plana, así que un rango enorme de x produce valores que un double no puede distinguir. La ubicación solo se puede recuperar hasta más o menos la raíz cuadrada del épsilon de máquina.
Si el problema pide el valor mínimo, la búsqueda ternaria es exacta. Si pide dónde está el mínimo, obtienes la mitad de los dígitos.
Costo: O(iteraciones): cada paso conserva dos tercios del intervalo, así que converge más despacio que la búsqueda binaria pero aún de forma geométrica.
Úsalo cuando la cantidad claramente baje y luego suba. Unimodal es el requisito, y es un requisito real: en una función con dos hondonadas, esto converge con toda confianza a la equivocada.
Qué recordar
-
Un resultado negativo de
Array.BinarySearches~insertionPoint. No es un error. Aplica~y tienes dónde va. -
Las cotas
loweryupperresponden preguntas que la búsqueda de la BCL no puede.upper - loweres cuántas copias existen, y la igualdad significa que no está. -
La búsqueda binaria no necesita un arreglo ordenado. Necesita una pregunta sí/no que cambie exactamente una vez. Ese requisito es mucho más débil, y es por eso que el patrón se aplica a problemas que no contienen ninguna colección.
-
Comprueba la monotonía antes de escribir nada. Si «funciona con 20» no implica «funciona con 21», la búsqueda es inválida por muy cuidadosamente que la programes.
-
Las cotas holgadas están bien; las cotas equivocadas no. El elemento más pesado y la suma total son ambos obviamente correctos, y O(log) hace que la holgura salga gratis.
-
Con números reales, cuenta iteraciones, no precisión. Cien siempre bastan y nunca pueden colgarse. Una condición de épsilon sí.
-
La búsqueda ternaria localiza un mínimo con la mitad de los dígitos con los que lo evalúa. Es la planitud cerca del mínimo, no un error de programación.
La parte 5 pasa de la búsqueda a los contenedores: pilas, colas, y las estructuras monótonas que responden «cuál es lo siguiente más grande» en un solo recorrido.