---
title: "Busca por Interpolação em Zig — Implementação e Explicação"
url: "https://ziglang.com.br/algoritmos/busca-por-interpola%C3%A7%C3%A3o-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/"
markdown_url: "https://ziglang.com.br/algoritmos/busca-por-interpola%C3%A7%C3%A3o-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD"
description: "Aprenda o algoritmo de Busca por Interpolação implementado em Zig. Busca adaptativa baseada na distribuição dos dados com análise completa."
date: "2026-02-21"
author: "Zig Brasil"
---

# Busca por Interpolação em Zig — Implementação e Explicação

Aprenda o algoritmo de Busca por Interpolação implementado em Zig. Busca adaptativa baseada na distribuição dos dados com análise completa.


# Busca por Interpolação em Zig — Implementação e Explicação

A **Busca por Interpolação** é uma variante da [busca binária](/algoritmos/busca-binaria/) 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

```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](/algoritmos/busca-binaria/) nesses casos.

## Recursos Relacionados

- [Busca Binária em Zig](/algoritmos/busca-binaria/) — Busca clássica O(log n)
- [Busca Exponencial em Zig](/algoritmos/busca-exponencial/) — Para arrays de tamanho desconhecido
- [Busca Linear em Zig](/algoritmos/busca-linear/) — Para dados não ordenados
- [Array Estático](/estruturas-dados/array-estatico/) — Estrutura ideal para busca por interpolação
- [Hash Table](/estruturas-dados/hash-table/) — Alternativa O(1) para busca exata