---
title: "Busca Ternária em Zig: Funções Unimodais, Máximo e Mínimo"
url: "https://ziglang.com.br/algoritmos/busca-ternaria/"
markdown_url: "https://ziglang.com.br/algoritmos/busca-ternaria.MD"
description: "Implemente busca ternária em Zig para encontrar máximo ou mínimo de funções unimodais, com versão contínua, discreta, testes e análise de precisão."
date: "2026-02-21"
author: "Zig Brasil"
---

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

Implemente busca ternária em Zig para encontrar máximo ou mínimo de funções unimodais, com versão contínua, discreta, testes e análise de precisão.


# 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.

| Problema | Busca ternária funciona? | Observação |
|---|---|---|
| Máximo de uma função que cresce e depois decresce | Sim | Caso clássico de pico unimodal |
| Mínimo de uma função que decresce e depois cresce | Sim | Inverta a comparação |
| Maior elemento de um array unimodal | Sim | Use índices inteiros |
| Localizar um valor em array ordenado | Funciona, mas não é recomendada | Busca binária costuma fazer menos comparações |
| Função com vários picos locais | Não há garantia | O resultado pode ser apenas um ótimo local |
| Dados sem ordem ou sem unimodalidade | Não | Use outra estratégia |

Imagine a função contínua abaixo:

```text
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.

```zig
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`:

```zig
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:

```text
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`.

```zig
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`:

```zig
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.

```zig
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:

```zig
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:

```text
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:

```zig
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:

```text
(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:

```zig
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:

```bash
zig test busca_ternaria.zig
```

## Complexidade

| Versão | Tempo | Espaço auxiliar |
|---|---:|---:|
| Função contínua com `epsilon` | `O(log((R - L) / epsilon))` | `O(1)` |
| Função contínua com `k` iterações | `O(k)` | `O(1)` |
| Array unimodal com `n` itens | `O(log n)` | `O(1)` |

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](/algoritmos/busca-exponencial/) e [exponenciação rápida](/algoritmos/exponenciacao-rapida/). Para comparar com uma busca que aproveita a distribuição dos valores de um array ordenado, consulte [busca por interpolação](/algoritmos/busca-interpolacao/).

## 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.