--- title: "Busca Binária em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/busca-bin%C3%A1ria-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/busca-bin%C3%A1ria-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o algoritmo de Busca Binária implementado em Zig. Explicação completa com código funcional, variações e análise de complexidade O(log n)." date: "2026-02-21" author: "Zig Brasil" --- # Busca Binária em Zig — Implementação e Explicação Aprenda o algoritmo de Busca Binária implementado em Zig. Explicação completa com código funcional, variações e análise de complexidade O(log n). # Busca Binária em Zig — Implementação e Explicação A **Busca Binária** é um algoritmo eficiente para encontrar um elemento em um array **ordenado**. A cada passo, ela divide o espaço de busca pela metade, comparando o elemento do meio com o valor procurado. ## Como Funciona 1. Defina os limites: `esquerda = 0`, `direita = n - 1` 2. Calcule o meio: `meio = esquerda + (direita - esquerda) / 2` 3. Compare o elemento do meio com o alvo: - Se igual: encontrado! - Se alvo é menor: busque na metade esquerda - Se alvo é maior: busque na metade direita 4. Repita até encontrar ou esgotar o espaço ### Visualização do Processo ``` Array ordenado: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] Procurando: 23 Passo 1: esq=0, dir=9, meio=4 [2, 5, 8, 12, [16], 23, 38, 56, 72, 91] 16 < 23 → busca na metade direita Passo 2: esq=5, dir=9, meio=7 [2, 5, 8, 12, 16, 23, 38, [56], 72, 91] 56 > 23 → busca na metade esquerda Passo 3: esq=5, dir=6, meio=5 [2, 5, 8, 12, 16, [23], 38, 56, 72, 91] 23 = 23 ✓ Encontrado na posição 5! Total: 3 comparações (vs 6 na busca linear) ``` ## Implementação em Zig ```zig const std = @import("std"); /// Busca binária iterativa — retorna o índice ou null. pub fn buscaBinaria(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 meio = esquerda + (direita - esquerda) / 2; if (items[meio] == alvo) { return meio; } else if (items[meio] < alvo) { esquerda = meio + 1; } else { if (meio == 0) break; direita = meio - 1; } } return null; } /// Busca binária recursiva. pub fn buscaBinariaRecursiva( comptime T: type, items: []const T, alvo: T, esquerda: usize, direita: usize, ) ?usize { if (esquerda > direita) return null; const meio = esquerda + (direita - esquerda) / 2; if (items[meio] == alvo) return meio; if (items[meio] < alvo) { return buscaBinariaRecursiva(T, items, alvo, meio + 1, direita); } if (meio == 0) return null; return buscaBinariaRecursiva(T, items, alvo, esquerda, meio - 1); } /// Lower bound: encontra a primeira posição onde o valor poderia ser inserido /// mantendo a ordenação (primeiro índice >= alvo). pub fn lowerBound(comptime T: type, items: []const T, alvo: T) usize { var esquerda: usize = 0; var direita: usize = items.len; while (esquerda < direita) { const meio = esquerda + (direita - esquerda) / 2; if (items[meio] < alvo) { esquerda = meio + 1; } else { direita = meio; } } return esquerda; } /// Upper bound: encontra a primeira posição após o alvo /// (primeiro índice > alvo). pub fn upperBound(comptime T: type, items: []const T, alvo: T) usize { var esquerda: usize = 0; var direita: usize = items.len; while (esquerda < direita) { const meio = esquerda + (direita - esquerda) / 2; if (items[meio] <= alvo) { esquerda = meio + 1; } else { direita = meio; } } return esquerda; } /// Conta quantas vezes um valor aparece no array ordenado. pub fn contarOcorrencias(comptime T: type, items: []const T, alvo: T) usize { return upperBound(T, items, alvo) - lowerBound(T, items, alvo); } /// Busca binária em array de floats com tolerância (epsilon). pub fn buscaBinariaFloat(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) { const meio = esquerda + (direita - esquerda) / 2; if (@abs(items[meio] - alvo) < epsilon) return meio; if (items[meio] < alvo) { esquerda = meio + 1; } else { if (meio == 0) break; direita = meio - 1; } } return null; } pub fn main() !void { const stdout = std.io.getStdOut().writer(); const nums = [_]i32{ 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 }; // Busca simples if (buscaBinaria(i32, &nums, 23)) |idx| { try stdout.print("23 encontrado na posição {d}\n", .{idx}); } // Lower e Upper bound const dados = [_]i32{ 1, 2, 2, 2, 3, 4, 5 }; const lb = lowerBound(i32, &dados, 2); const ub = upperBound(i32, &dados, 2); try stdout.print("Valor 2: lower_bound={d}, upper_bound={d}, ocorrências={d}\n", .{ lb, ub, contarOcorrencias(i32, &dados, 2), }); // Busca recursiva if (buscaBinariaRecursiva(i32, &nums, 56, 0, nums.len - 1)) |idx| { try stdout.print("56 encontrado recursivamente na posição {d}\n", .{idx}); } } ``` ## Análise de Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | **Melhor caso** | O(1) — elemento no meio | O(1) iterativo | | **Caso médio** | O(log n) | O(1) iterativo | | **Pior caso** | O(log n) | O(1) iterativo / O(log n) recursivo | ### Por que O(log n)? A cada iteração, o espaço de busca é reduzido pela metade. Para n elementos: n → n/2 → n/4 → ... → 1. Isso requer `log₂(n)` passos. Para 1.000.000 de elementos: apenas ~20 comparações! ## Armadilhas Comuns 1. **Overflow no cálculo do meio**: `(esquerda + direita) / 2` pode causar overflow. Use `esquerda + (direita - esquerda) / 2` 2. **Array não ordenado**: o resultado será incorreto 3. **Elementos duplicados**: use lower_bound/upper_bound para controle preciso 4. **Underflow com usize**: `direita - 1` quando direita é 0 causa underflow em Zig (usize é unsigned) ## Variações na stdlib do Zig O Zig oferece `std.sort.binarySearch` na biblioteca padrão. Consulte a [documentação da stdlib](/stdlib/) para detalhes. ## Recursos Relacionados - [Busca Linear em Zig](/algoritmos/busca-linear/) — Alternativa para dados não ordenados - [Busca por Interpolação](/algoritmos/busca-interpolacao/) — Variante para dados uniformemente distribuídos - [Busca Exponencial](/algoritmos/busca-exponencial/) — Para arrays de tamanho desconhecido - [Busca Ternária](/algoritmos/busca-ternaria/) — Para funções unimodais - [Árvore de Busca Binária](/estruturas-dados/arvore-busca-binaria/) — Estrutura dinâmica com busca O(log n)