--- title: "Busca Ternária em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/busca-tern%C3%A1ria-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/busca-tern%C3%A1ria-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o algoritmo de Busca Ternária implementado em Zig. Busca para funções unimodais dividindo o espaço em três partes, com código e análise." date: "2026-02-21" author: "Zig Brasil" --- # Busca Ternária em Zig — Implementação e Explicação Aprenda o algoritmo de Busca Ternária implementado em Zig. Busca para funções unimodais dividindo o espaço em três partes, com código e análise. # Busca Ternária em Zig — Implementação e Explicação A **Busca Ternária** é um algoritmo que divide o espaço de busca em três partes iguais. Embora para busca simples em arrays ela seja menos eficiente que a [busca binária](/algoritmos/busca-binaria/), seu principal uso é encontrar o **máximo ou mínimo de funções unimodais** (funções que têm apenas um pico ou vale). ## Como Funciona ### Para Arrays Ordenados 1. Divida o array em três partes usando dois pontos: `m1 = esq + (dir - esq) / 3` e `m2 = dir - (dir - esq) / 3` 2. Compare o alvo com os elementos em m1 e m2 3. Descarte o terço que não pode conter o alvo ### Para Funções Unimodais (Principal Aplicação) 1. Avalie a função em m1 e m2 2. Se f(m1) < f(m2): o máximo está em [m1, dir] 3. Se f(m1) > f(m2): o máximo está em [esq, m2] 4. Repita até a precisão desejada ### Visualização ``` Busca em array: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] esq m1 m2 dir 0 3 6 9 Função unimodal (encontrar máximo): * * * * * * * * * esq m1 m2 dir Se f(m1) < f(m2), o pico está à direita de m1 ``` ## Implementação em Zig ```zig const std = @import("std"); /// Busca ternária em array ordenado. pub fn buscaTernaria(comptime T: type, items: []const T, alvo: T) ?usize { if (items.len == 0) return null; var esquerda: usize = 0; var direita: usize = items.len - 1; while (esquerda <= direita) { const terco = (direita - esquerda) / 3; const m1 = esquerda + terco; const m2 = direita - terco; if (items[m1] == alvo) return m1; if (items[m2] == alvo) return m2; if (alvo < items[m1]) { // Alvo está no primeiro terço if (m1 == 0) break; direita = m1 - 1; } else if (alvo > items[m2]) { // Alvo está no último terço esquerda = m2 + 1; } else { // Alvo está no terço do meio esquerda = m1 + 1; if (m2 == 0) break; direita = m2 - 1; } } return null; } /// Busca ternária para encontrar o MÁXIMO de uma função unimodal. /// A função deve ter exatamente um máximo no intervalo [esq, dir]. pub fn maximoUnimodal( comptime f: fn (f64) f64, esq: f64, dir: f64, epsilon: f64, ) f64 { var a = esq; var b = dir; while (b - a > epsilon) { const terco = (b - a) / 3.0; const m1 = a + terco; const m2 = b - terco; if (f(m1) < f(m2)) { a = m1; } else { b = m2; } } return (a + b) / 2.0; } /// Busca ternária para encontrar o MÍNIMO de uma função unimodal. pub fn minimoUnimodal( comptime f: fn (f64) f64, esq: f64, dir: f64, epsilon: f64, ) f64 { var a = esq; var b = dir; while (b - a > epsilon) { const terco = (b - a) / 3.0; const m1 = a + terco; const m2 = b - terco; if (f(m1) > f(m2)) { a = m1; } else { b = m2; } } return (a + b) / 2.0; } /// Busca ternária discreta — encontra o índice do máximo em um /// array unimodal (cresce e depois decresce). pub fn maximoArrayUnimodal(items: []const f64) ?usize { if (items.len == 0) return null; if (items.len == 1) return 0; var esquerda: usize = 0; var direita: usize = items.len - 1; while (direita - esquerda > 2) { const terco = (direita - esquerda) / 3; const m1 = esquerda + terco; const m2 = direita - terco; if (items[m1] < items[m2]) { esquerda = m1; } else { direita = m2; } } // Encontra o máximo no intervalo restante var max_idx = esquerda; var i = esquerda + 1; while (i <= direita) : (i += 1) { if (items[i] > items[max_idx]) max_idx = i; } return max_idx; } // Funções de exemplo fn parabolaInvertida(x: f64) f64 { // Máximo em x = 3 return -(x - 3.0) * (x - 3.0) + 9.0; } fn funcaoQuadratica(x: f64) f64 { // Mínimo em x = 2 return (x - 2.0) * (x - 2.0) + 1.0; } pub fn main() !void { const stdout = std.io.getStdOut().writer(); // Busca em array ordenado const nums = [_]i32{ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 }; if (buscaTernaria(i32, &nums, 11)) |idx| { try stdout.print("11 encontrado na posição {d}\n", .{idx}); } // Encontrar máximo de função unimodal const x_max = maximoUnimodal(parabolaInvertida, 0.0, 6.0, 1e-9); try stdout.print("Máximo de -(x-3)²+9 em x = {d:.6}\n", .{x_max}); try stdout.print("f(x_max) = {d:.6}\n", .{parabolaInvertida(x_max)}); // Encontrar mínimo const x_min = minimoUnimodal(funcaoQuadratica, -5.0, 10.0, 1e-9); try stdout.print("Mínimo de (x-2)²+1 em x = {d:.6}\n", .{x_min}); // Array unimodal const unimodal = [_]f64{ 1, 4, 8, 15, 20, 18, 12, 7, 3 }; if (maximoArrayUnimodal(&unimodal)) |idx| { try stdout.print("Máximo do array unimodal: posição {d}, valor {d}\n", .{ idx, unimodal[idx] }); } } ``` ## Análise de Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | **Array** | O(log₃ n) ≈ O(log n) | O(1) | | **Função contínua** | O(log(intervalo/epsilon)) | O(1) | ### Busca Ternária vs Busca Binária em Arrays A busca ternária faz 2 comparações por iteração e reduz por 1/3, enquanto a binária faz 1 comparação e reduz por 1/2. Comparando: - Ternária: `2 × log₃(n)` comparações - Binária: `1 × log₂(n)` comparações - `2 × log₃(n) > log₂(n)`, portanto a binária é mais eficiente para arrays! A vantagem da ternária é para **funções unimodais**, onde a binária não se aplica diretamente. ## Quando Usar - **Encontrar máximo/mínimo de funções unimodais**: principal aplicação - **Problemas de otimização**: programação competitiva - **Nunca para arrays ordenados**: use [busca binária](/algoritmos/busca-binaria/) que é mais eficiente ## Recursos Relacionados - [Busca Binária em Zig](/algoritmos/busca-binaria/) — Mais eficiente para arrays ordenados - [Busca por Interpolação](/algoritmos/busca-interpolacao/) — Para dados uniformes - [Busca Exponencial](/algoritmos/busca-exponencial/) — Para tamanho desconhecido - [Fibonacci com DP](/algoritmos/fibonacci-dp/) — Busca de Fibonacci como alternativa - [Heap Binário](/estruturas-dados/heap-binario/) — Para encontrar máximo/mínimo