Encontrar um valor num array ordenado é a coisa menos útil que a busca binária faz. O padrão que importa busca num espaço de respostas que ninguém nunca construiu, e não precisa de array ordenado nenhum.
Quase todo mundo sabe escrever busca binária sobre um array ordenado. Quase ninguém pensa nela quando o problema nunca menciona um array.
É dessa lacuna que esta parte trata. Quatro dos cinco padrões aqui não buscam em nenhuma coleção.
Todo programa abaixo está completo, foi rodado no .NET 10, e a saída dele está colada da execução.
Padrão 16 — O que Array.BinarySearch te dá, e o que não dá
A BCL já tem isso, e o valor de retorno quando não encontra é o recurso mais desperdiçado da classe inteira.
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}");
}Ele 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=0Um resultado negativo não é um código de erro. Ele é ~insertionPoint — o complemento bit a bit de onde o valor iria ficar. ~(-5) é 4, então 25 pertence ao índice 4. Essa única linha substitui uma segunda busca em um monte de problemas.
O que Array.BinarySearch não faz é dizer qual duplicata você achou. Com três cópias de 20 no array, a documentação promete só que você recebe uma delas. Por isso vale ter os dois limites na mão, e o par responde mais perguntas do que cada um sozinho.
lower é o primeiro índice não menor que x; upper é o primeiro índice maior que x. A distância entre eles é quantas cópias existem, e quando coincidem o valor não está lá — que é também exatamente onde ele seria inserido.
Repare que os dois são while (lo < hi) com hi começando em a.Length, não a.Length - 1. Isso é de propósito — a resposta pode legitimamente ser “depois do fim”, que é o que acontece com 50.
Custo: O(log n).
Use quando você precisa de uma contagem de valores iguais, de um ponto de inserção, ou do primeiro elemento pelo menos tão grande quanto algum limite. upper - lower é a contagem, e nenhuma varredura separada é necessária.
Padrão 17 — Busca binária na resposta
Aqui está o que realmente importa.
Os pacotes têm que ser enviados em ordem, ao longo de D dias. Escolha a menor capacidade diária que entrega tudo a tempo.
Não existe array para buscar. Mas olhe o formato da pergunta. Se a capacidade 20 funciona, então 21 funciona, e 22, e tudo acima. Se 14 falha, 13 falha, e tudo abaixo. Então as respostas, postas em ordem, ficam assim:
capacity: 10 11 12 13 14 15 16 17 18 19 20
works? F F F F F T T T T T TIsso vira exatamente uma vez, e achar onde algo vira exatamente uma vez é o que a busca binária é. O array ordenado nunca foi o requisito — ele era um jeito de conseguir essa propriedade.
A busca binária não precisa de um array ordenado. Ela precisa de uma pergunta cuja resposta vira exatamente uma vez. Aqui o array nunca é construído — o predicado é avaliado sob demanda, e a busca persegue a fronteira entre o último F e o primeiro 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)}");Ele 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: FalseTrês coisas fazem isso funcionar, e elas são o checklist para todo problema desse formato:
- Um teste de viabilidade.
Feasibleresponde sim ou não para um candidato. É uma passada gulosa simples, e ela tem permissão de ser meio lenta — roda só O(log intervalo) vezes. - Monotonicidade. Uma vez verdadeiro, sempre verdadeiro para cima. Se isso falha, a abordagem inteira é inválida, e essa é a coisa para checar antes de escrever qualquer código.
- Limites que são obviamente corretos.
loé o pacote mais pesado, porque nada menor consegue enviá-lo.hié o total, porque isso sempre termina em um dia. Nenhum dos dois precisa ser apertado — só certo.
As duas últimas linhas impressas são o hábito que vale manter: garanta que a resposta funciona e que a de baixo dela não funciona. Isso pega um erro de um na hora.
Custo: O(viabilidade × log intervalo).
Use quando o problema disser minimize o máximo, maximize o mínimo, ou o menor X tal que. Essa formulação é quase uma garantia.
Padrão 18 — O array rotacionado
Um array ordenado, rotacionado num ponto desconhecido. Encontre um alvo em O(log n).
O instinto é achar o ponto de rotação primeiro, e depois buscar. Isso funciona, e são duas buscas. Esta aqui é uma.
Em qualquer divisão, o corte da rotação só pode cair em uma metade — só existe um corte. Então a outra metade está de fato ordenada, e você pode raciocinar sobre ela normalmente.
A comparação a[lo] ≤ a[mid] é o truque inteiro. Ela não testa o alvo — ela identifica sobre qual metade você pode raciocinar normalmente.
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");
}Ele 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
-> -1A comparação a[lo] <= a[mid] não tem nada a ver com o alvo. Ela pergunta qual metade está intacta. Só então o alvo é testado, contra o intervalo conhecido daquela metade.
Olhe a execução de target 3: ela nunca acha nada, e mesmo assim corta a busca pela metade a cada passo, terminando em três comparações em vez de sete.
Custo: O(log n).
Use quando os dados estão ordenados mas deslocados — arrays rotacionados, buffers circulares, um arquivo de log que deu a volta.
Padrão 19 — Busca binária em números reais
Mesma ideia, domínio contínuo. Não existe um “próximo” valor para onde pular, então o laço não pode terminar em lo == hi.
A correção errada é while (hi - lo > 1e-9). Perto dos limites da precisão de um double, (lo + hi) / 2 pode ser exatamente igual a lo, o intervalo para de encolher, e o laço nunca acaba. Ele passa em todo teste que você escreve e trava no juiz.
A correção certa é parar de contar precisão e contar iterações.
// 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}");
}Ele 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-031Cem divisões pela metade reduzem qualquer intervalo inicial por um fator de 2⁻¹⁰⁰, que é cerca de 7,9 × 10⁻³¹ — muito abaixo de qualquer coisa que um double consegue representar. Então cem iterações são sempre suficientes, não custam nada, e não podem entrar em laço infinito. Cinquenta normalmente já basta. Use cem e pare de pensar nisso.
Custo: O(iterações), uma constante fixa.
Use quando a resposta for um número real — uma taxa, uma razão, uma distância, um tempo.
Padrão 20 — Busca ternária, quando a resposta não é monotônica
A busca binária precisa que a resposta sim/não vire uma vez. Alguns problemas não te dão isso. Uma função que cai e depois sobe não tem ponto de virada — ela tem um mínimo, e dos dois lados dele a função vai na direção errada.
Uma sondagem não diz de que lado do mínimo você está. Duas dizem.
A busca binária precisa que a resposta de uma pergunta sim/não vire uma vez. A busca ternária precisa de menos: só que a função caia e depois suba. Duas sondagens dizem qual terço externo não pode conter o 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}");Ele 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.00000000Agora olhe de perto essa resposta: x = 2.50000001, mas f(x) = 1.00000000.
O valor da função está certo até dezesseis dígitos, enquanto a localização só está certa até oito. Isso não é um bug no laço, e mais iterações não vão consertar. Perto de um mínimo, uma função suave é plana, então uma faixa enorme de x produz valores que um double não consegue distinguir. A localização só é recuperável até mais ou menos a raiz quadrada do epsilon de máquina.
Se o problema pede o valor mínimo, a busca ternária é exata. Se ele pergunta onde está o mínimo, você recebe metade dos dígitos.
Custo: O(iterações) — cada passo mantém dois terços do intervalo, então ela converge mais devagar que a busca binária, mas ainda assim geometricamente.
Use quando a grandeza claramente cai e depois sobe. Unimodal é o requisito, e é um requisito de verdade — numa função com duas depressões, isso converge com toda a confiança para a errada.
O que lembrar
-
Um resultado negativo de
Array.BinarySearché~insertionPoint. Não é um erro. Aplique~e você tem onde ele pertence. -
Os limites
lowereupperrespondem perguntas que a busca da BCL não responde.upper - loweré quantas cópias existem, e igualdade significa ausente. -
A busca binária não precisa de um array ordenado. Ela precisa de uma pergunta sim/não que vira exatamente uma vez. Esse é um requisito bem mais fraco, e é por isso que o padrão se aplica a problemas que não contêm coleção nenhuma.
-
Cheque a monotonicidade antes de escrever qualquer coisa. Se “funciona em 20” não implica “funciona em 21”, a busca é inválida por mais cuidadoso que seja o código.
-
Limites folgados tudo bem; limites errados não. O item mais pesado e a soma total são os dois obviamente corretos, e o O(log) faz a folga sair de graça.
-
Em números reais, conte iterações, não precisão. Cem é sempre suficiente e nunca pode travar. Uma condição de epsilon pode.
-
A busca ternária localiza um mínimo com metade dos dígitos com que o avalia. É a planura perto do mínimo, não um erro de código.
A parte 5 sai da busca e vai para os contêineres: pilhas, filas, e as estruturas monotônicas que respondem “qual é a próxima coisa maior” em uma passada.