Busca por Interpolação em Zig — Implementação e Explicação
A Busca por Interpolação é uma variante da busca binária que estima a posição do elemento procurado com base na distribuição dos valores. Em vez de sempre dividir ao meio, ela calcula uma posição proporcional — semelhante a como procuramos uma palavra no dicionário (abrimos mais perto do início para palavras com “A” e mais perto do fim para palavras com “Z”).
Como Funciona
Em vez de usar meio = (esquerda + direita) / 2, calcula:
pos = esquerda + ((alvo - items[esquerda]) * (direita - esquerda))
/ (items[direita] - items[esquerda])
Essa fórmula assume que os valores estão distribuídos uniformemente e estima onde o alvo provavelmente está.
Visualização do Processo
Array: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Procurando: 70
Busca Binária: meio = (0+9)/2 = 4 → items[4]=50 → direita
meio = (5+9)/2 = 7 → items[7]=80 → esquerda
meio = (5+6)/2 = 5 → items[5]=60 → direita
meio = (6+6)/2 = 6 → items[6]=70 ✓ (4 passos)
Busca Interpolação:
pos = 0 + ((70-10)*(9-0))/(100-10) = 0 + (60*9)/90 = 6
items[6] = 70 ✓ (1 passo!)
Implementação em Zig
const std = @import("std");
/// Busca por interpolação para inteiros em array ordenado.
/// Retorna o índice do elemento ou null se não encontrado.
pub fn buscaInterpolacao(items: []const i64, alvo: i64) ?usize {
if (items.len == 0) return null;
var esquerda: usize = 0;
var direita: usize = items.len - 1;
while (esquerda <= direita and alvo >= items[esquerda] and alvo <= items[direita]) {
// Se o intervalo tem um único elemento
if (esquerda == direita) {
if (items[esquerda] == alvo) return esquerda;
return null;
}
// Calcula a posição estimada por interpolação
const numerador: i64 = (alvo - items[esquerda]) * @as(i64, @intCast(direita - esquerda));
const denominador: i64 = items[direita] - items[esquerda];
if (denominador == 0) {
// Todos os valores no intervalo são iguais
if (items[esquerda] == alvo) return esquerda;
return null;
}
const pos: usize = esquerda + @as(usize, @intCast(@divFloor(numerador, denominador)));
if (items[pos] == alvo) {
return pos;
} else if (items[pos] < alvo) {
esquerda = pos + 1;
} else {
if (pos == 0) return null;
direita = pos - 1;
}
}
return null;
}
/// Versão genérica usando floats para a interpolação.
pub fn buscaInterpolacaoFloat(items: []const f64, alvo: f64, epsilon: f64) ?usize {
if (items.len == 0) return null;
var esquerda: usize = 0;
var direita: usize = items.len - 1;
while (esquerda <= direita and alvo >= items[esquerda] - epsilon and alvo <= items[direita] + epsilon) {
if (esquerda == direita) {
if (@abs(items[esquerda] - alvo) < epsilon) return esquerda;
return null;
}
const range_val = items[direita] - items[esquerda];
if (@abs(range_val) < epsilon) {
if (@abs(items[esquerda] - alvo) < epsilon) return esquerda;
return null;
}
const frac = (alvo - items[esquerda]) / range_val;
const range_idx: f64 = @floatFromInt(direita - esquerda);
const pos: usize = esquerda + @as(usize, @intFromFloat(frac * range_idx));
if (@abs(items[pos] - alvo) < epsilon) {
return pos;
} else if (items[pos] < alvo) {
esquerda = pos + 1;
} else {
if (pos == 0) return null;
direita = pos - 1;
}
}
return null;
}
pub fn main() !void {
const stdout = std.io.getStdOut().writer();
// Dados uniformemente distribuídos — caso ideal
const uniforme = [_]i64{ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
if (buscaInterpolacao(&uniforme, 70)) |idx| {
try stdout.print("70 encontrado na posição {d}\n", .{idx});
}
if (buscaInterpolacao(&uniforme, 55)) |_| {
try stdout.print("55 encontrado\n", .{});
} else {
try stdout.print("55 não encontrado\n", .{});
}
// Busca com floats
const floats = [_]f64{ 1.0, 2.5, 4.0, 5.5, 7.0, 8.5, 10.0 };
if (buscaInterpolacaoFloat(&floats, 5.5, 0.001)) |idx| {
try stdout.print("5.5 encontrado na posição {d}\n", .{idx});
}
}
Análise de Complexidade
| Caso | Tempo | Espaço |
|---|---|---|
| Melhor caso | O(1) | O(1) |
| Caso médio (uniforme) | O(log log n) | O(1) |
| Pior caso | O(n) — dados exponencialmente distribuídos | O(1) |
Por que O(log log n)?
Para dados uniformemente distribuídos, cada estimativa reduz o espaço de busca exponencialmente mais do que a busca binária. Enquanto a binária leva log(n) passos, a interpolação leva apenas log(log(n)).
Para 1.000.000.000 de elementos uniformes: ~5 comparações (vs ~30 na busca binária)!
Comparação com Busca Binária
| Aspecto | Busca Binária | Busca Interpolação |
|---|---|---|
| Melhor caso | O(1) | O(1) |
| Caso médio | O(log n) | O(log log n) |
| Pior caso | O(log n) | O(n) |
| Distribuição | Qualquer | Uniforme ideal |
| Complexidade de código | Simples | Moderada |
Quando Usar
- Dados uniformemente distribuídos: IDs sequenciais, timestamps regulares
- Arrays muito grandes: a diferença entre log(n) e log(log(n)) é significativa
- Valores numéricos: a fórmula de interpolação precisa de aritmética
Evite quando os dados são muito desiguais (exponenciais, clusters) — use busca binária nesses casos.
Recursos Relacionados
- Busca Binária em Zig — Busca clássica O(log n)
- Busca Exponencial em Zig — Para arrays de tamanho desconhecido
- Busca Linear em Zig — Para dados não ordenados
- Array Estático — Estrutura ideal para busca por interpolação
- Hash Table — Alternativa O(1) para busca exata