Busca Ternária em Zig: Funções Unimodais, Máximo e Mínimo

A busca ternária em Zig é mais útil para encontrar o máximo ou mínimo de uma função unimodal: uma função que cresce e depois decresce, ou que decresce e depois cresce, dentro de um intervalo conhecido. A cada iteração, o algoritmo calcula dois pontos internos, compara os valores da função e descarta a parte que não pode conter o ótimo.

A resposta direta é: use busca ternária quando houver uma garantia de unimodalidade. Para procurar um valor comum em um array ordenado, prefira busca binária; apesar do nome, dividir em três partes não torna a busca ternária automaticamente mais rápida, porque ela precisa de mais comparações por iteração.

Quando a busca ternária é a escolha certa

A técnica se aplica quando o domínio está ordenado e existe apenas uma mudança de direção relevante.

Imagine a função contínua abaixo:

valor
  ^
  |              *
  |           *     *
  |        *           *
  |     *                 *
  +--------------------------------> x
        L     m1    m2           R

Para encontrar o máximo, avaliamos f(m1) e f(m2):

• se f(m1) < f(m2), a função ainda está subindo entre os pontos; o máximo não está antes de m1, então movemos o limite esquerdo;
• se f(m1) > f(m2), a função já está descendo; o máximo não está depois de m2, então movemos o limite direito;
• se os valores forem iguais, o ótimo permanece no intervalo central e podemos descartar as extremidades.

Essa decisão só é válida porque a função é unimodal no intervalo informado.

Implementação contínua para encontrar o máximo

Uma implementação robusta deve validar o intervalo e a precisão. Também é útil limitar as iterações: com f64, chega um momento em que o arredondamento impede os limites de avançarem, mesmo que a condição baseada em epsilon ainda pareça verdadeira.

const std = @import("std");

pub const BuscaError = error{
    IntervaloInvalido,
    PrecisaoInvalida,
};

pub fn maximoUnimodal(
    comptime funcao: fn (f64) f64,
    esquerda_inicial: f64,
    direita_inicial: f64,
    epsilon: f64,
) BuscaError!f64 {
    if (esquerda_inicial > direita_inicial) {
        return error.IntervaloInvalido;
    }
    if (!(epsilon > 0.0) or !std.math.isFinite(epsilon)) {
        return error.PrecisaoInvalida;
    }

    var esquerda = esquerda_inicial;
    var direita = direita_inicial;
    var iteracoes: usize = 0;

    while (direita - esquerda > epsilon and iteracoes < 256) {
        const terco = (direita - esquerda) / 3.0;
        const m1 = esquerda + terco;
        const m2 = direita - terco;

        // O arredondamento de f64 pode impedir progresso em intervalos
        // extremamente pequenos.
        if (m1 == esquerda or m2 == direita or m1 == m2) break;

        const y1 = funcao(m1);
        const y2 = funcao(m2);

        if (y1 < y2) {
            esquerda = m1;
        } else if (y1 > y2) {
            direita = m2;
        } else {
            esquerda = m1;
            direita = m2;
        }

        iteracoes += 1;
    }

    return esquerda + (direita - esquerda) / 2.0;
}

O retorno é uma aproximação da coordenada x onde ocorre o máximo. Para obter o valor máximo, avalie a função mais uma vez no ponto retornado.

Exemplo: máximo de uma parábola invertida

A função -(x - 3)² + 9 possui máximo em x = 3:

fn parabolaInvertida(x: f64) f64 {
    return -(x - 3.0) * (x - 3.0) + 9.0;
}

pub fn main() !void {
    const x = try maximoUnimodal(
        parabolaInvertida,
        0.0,
        6.0,
        1e-9,
    );

    std.debug.print("x aproximado: {d:.9}\n", .{x});
    std.debug.print("valor máximo: {d:.9}\n", .{
        parabolaInvertida(x),
    });
}

A saída ficará próxima de:

x aproximado: 3.000000000
valor máximo: 9.000000000

O algoritmo não “descobre” que se trata de uma parábola. Ele usa apenas o contrato de que existe um único pico no intervalo [0, 6].

Encontrando o mínimo de uma função unimodal

Para localizar um vale, inverta a comparação. Se f(m1) > f(m2), a função ainda está descendo e o mínimo está à direita de m1.

pub fn minimoUnimodal(
    comptime funcao: fn (f64) f64,
    esquerda_inicial: f64,
    direita_inicial: f64,
    epsilon: f64,
) BuscaError!f64 {
    if (esquerda_inicial > direita_inicial) {
        return error.IntervaloInvalido;
    }
    if (!(epsilon > 0.0) or !std.math.isFinite(epsilon)) {
        return error.PrecisaoInvalida;
    }

    var esquerda = esquerda_inicial;
    var direita = direita_inicial;
    var iteracoes: usize = 0;

    while (direita - esquerda > epsilon and iteracoes < 256) {
        const terco = (direita - esquerda) / 3.0;
        const m1 = esquerda + terco;
        const m2 = direita - terco;

        if (m1 == esquerda or m2 == direita or m1 == m2) break;

        const y1 = funcao(m1);
        const y2 = funcao(m2);

        if (y1 > y2) {
            esquerda = m1;
        } else if (y1 < y2) {
            direita = m2;
        } else {
            esquerda = m1;
            direita = m2;
        }

        iteracoes += 1;
    }

    return esquerda + (direita - esquerda) / 2.0;
}

Por exemplo, (x - 2)² + 1 possui mínimo em x = 2:

fn quadratica(x: f64) f64 {
    return (x - 2.0) * (x - 2.0) + 1.0;
}

const x_min = try minimoUnimodal(quadratica, -5.0, 10.0, 1e-9);

Versão discreta para array unimodal

Em um array unimodal, os valores aumentam até um pico e depois diminuem. Como os índices são inteiros, mantemos a busca ternária enquanto o intervalo é grande e examinamos diretamente as poucas posições restantes.

pub fn indiceDoMaximo(items: []const i64) ?usize {
    if (items.len == 0) return null;

    var esquerda: usize = 0;
    var direita: usize = items.len - 1;

    while (direita - esquerda > 3) {
        const terco = (direita - esquerda) / 3;
        const m1 = esquerda + terco;
        const m2 = direita - terco;

        if (items[m1] < items[m2]) {
            esquerda = m1 + 1;
        } else if (items[m1] > items[m2]) {
            direita = m2 - 1;
        } else {
            esquerda = m1;
            direita = m2;
        }
    }

    var melhor = esquerda;
    var i = esquerda + 1;
    while (i <= direita) : (i += 1) {
        if (items[i] > items[melhor]) melhor = i;
    }

    return melhor;
}

Uso:

const valores = [_]i64{ 1, 4, 8, 15, 20, 18, 12, 7, 3 };
const indice = indiceDoMaximo(&valores).?;

std.debug.print("índice: {d}, valor: {d}\n", .{
    indice,
    valores[indice],
});

O resultado é o índice 4, cujo valor é 20.

Se o array puder conter um platô, como { 1, 4, 8, 8, 8, 3 }, defina antes qual resposta deseja: qualquer índice máximo, o primeiro ou o último. A função acima devolve um dos máximos, mas não promete a extremidade do platô.

Busca ternária em array ordenado vale a pena?

É possível dividir um array ordenado em três regiões para localizar um alvo. Entretanto, isso raramente oferece vantagem prática sobre a busca binária.

Em termos aproximados:

busca ternária: 2 × log₃(n) comparações principais
busca binária:  1 × log₂(n) comparação principal

Embora a ternária reduza o espaço para cerca de um terço, ela compara o alvo com dois pontos. A binária reduz para metade com uma comparação central e tem implementação mais simples. Portanto:

• para encontrar um valor em array ordenado, use busca binária;
• para encontrar o ótimo de uma função unimodal, use busca ternária;
• para encontrar a primeira ou última ocorrência, use variantes de limite inferior ou superior da busca binária.

Essa distinção é importante porque muitos exemplos apresentam a busca em arrays como uso principal, quando a otimização unimodal é o caso em que a técnica realmente se destaca.

Como escolher epsilon ou o número de iterações

Na versão contínua, epsilon controla o tamanho final do intervalo, não garante diretamente a quantidade de casas decimais corretas no valor da função. A sensibilidade depende da escala e da curvatura do problema.

Uma alternativa previsível é executar um número fixo de iterações:

var iteracao: usize = 0;
while (iteracao < 100) : (iteracao += 1) {
    // calcula m1 e m2 e reduz o intervalo
}

Após k iterações, o intervalo mede aproximadamente:

(R - L) × (2/3)^k

Para f64, algo entre 80 e 150 iterações costuma ser mais que suficiente em intervalos comuns, mas o limite deve refletir a escala dos dados. Evite tolerâncias arbitrariamente menores que a precisão representável.

Testes em Zig

Os testes devem verificar máximo, mínimo, array vazio, array com um elemento e entradas inválidas:

test "encontra maximo de funcao unimodal" {
    const x = try maximoUnimodal(
        parabolaInvertida,
        0.0,
        6.0,
        1e-10,
    );
    try std.testing.expectApproxEqAbs(
        @as(f64, 3.0),
        x,
        1e-7,
    );
}

test "encontra minimo de funcao unimodal" {
    const x = try minimoUnimodal(
        quadratica,
        -5.0,
        10.0,
        1e-10,
    );
    try std.testing.expectApproxEqAbs(
        @as(f64, 2.0),
        x,
        1e-7,
    );
}

test "encontra pico de array unimodal" {
    const valores = [_]i64{ 1, 4, 8, 15, 20, 18, 12 };
    try std.testing.expectEqual(
        @as(?usize, 4),
        indiceDoMaximo(&valores),
    );
}

test "trata arrays de borda" {
    try std.testing.expectEqual(
        @as(?usize, null),
        indiceDoMaximo(&.{}),
    );
    try std.testing.expectEqual(
        @as(?usize, 0),
        indiceDoMaximo(&.{42}),
    );
}

test "rejeita precisao invalida" {
    try std.testing.expectError(
        error.PrecisaoInvalida,
        maximoUnimodal(parabolaInvertida, 0.0, 6.0, 0.0),
    );
}

Coloque as funções e os testes no mesmo arquivo e execute:

zig test busca_ternaria.zig

Complexidade

A base do logaritmo não muda a classe assintótica. A cada passo, o intervalo preservado possui aproximadamente dois terços do tamanho anterior.

Na prática, o custo de avaliar a função pode dominar completamente o custo do algoritmo. Se funcao(x) executa uma simulação cara, considere memorizar valores repetidos ou reformular a atualização para reaproveitar uma avaliação quando isso for possível e correto.

Erros comuns

1. Usar a técnica sem provar unimodalidade. Com vários picos, descartar uma região pode remover o ótimo global.
2. Inverter a comparação de máximo e mínimo. Para máximo, f(m1) < f(m2) move a esquerda; para mínimo, a mesma relação move a direita.
3. Aplicar busca ternária a qualquer array ordenado. Ela funciona, mas a busca binária geralmente é melhor para localizar valores.
4. Ignorar platôs. Empates precisam preservar uma região que ainda contenha uma resposta válida.
5. Aceitar epsilon <= 0. A condição de parada deixa de representar uma precisão válida.
6. Confiar apenas em ponto flutuante para terminar. Use também limite de iterações e verificação de progresso.
7. Confundir posição do ótimo com valor ótimo. A função retorna x; calcule f(x) se precisar do valor.
8. Escolher um intervalo que não contém o pico ou vale. A garantia é sempre relativa aos limites fornecidos.

Aplicações práticas

Busca ternária aparece em problemas de otimização de uma variável: escolher um parâmetro que minimiza custo, encontrar o ponto de maior rendimento em uma curva, ajustar uma distância em geometria computacional ou maximizar uma função de pontuação unimodal. Em programação competitiva, a afirmação do problema normalmente fornece explicitamente a propriedade unimodal.

Em software de produção, trate essa propriedade como parte do contrato. Documente o intervalo, as unidades, a tolerância e o comportamento diante de NaN, infinito ou falha durante a avaliação. Se a função vem de medições ruidosas, a sequência pode deixar de ser unimodal e exigir suavização, amostragem ou outro método de otimização.

Para continuar estudando técnicas logarítmicas, veja busca exponencial em Zig e exponenciação rápida. Para comparar com uma busca que aproveita a distribuição dos valores de um array ordenado, consulte busca por interpolação.

Resumo

A busca ternária reduz um intervalo usando dois pontos internos. Seu melhor uso não é substituir a busca binária em arrays, mas encontrar máximos e mínimos quando existe garantia de unimodalidade.

Ao implementar em Zig:

• valide intervalo e precisão;
• use comparações diferentes para máximo e mínimo;
• trate empates e platôs explicitamente;
• limite iterações em cálculos com f64;
• teste casos de borda e entradas inválidas;
• use busca binária quando a tarefa for apenas localizar um valor ordenado.

Com essas condições claras, a busca ternária oferece tempo logarítmico, espaço constante e uma implementação pequena para uma classe útil de problemas de otimização.