--- title: "Busca Exponencial em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/busca-exponencial-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/busca-exponencial-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o algoritmo de Busca Exponencial implementado em Zig. Busca eficiente em arrays ordenados de tamanho desconhecido, com código e análise." date: "2026-02-21" author: "Zig Brasil" --- # Busca Exponencial em Zig — Implementação e Explicação Aprenda o algoritmo de Busca Exponencial implementado em Zig. Busca eficiente em arrays ordenados de tamanho desconhecido, com código e análise. # Busca Exponencial em Zig — Implementação e Explicação A **Busca Exponencial** é um algoritmo que combina busca exponencial com [busca binária](/algoritmos/busca-binaria/). Primeiro, ela encontra um intervalo onde o elemento pode estar, dobrando o índice exponencialmente (1, 2, 4, 8, 16...). Depois, aplica busca binária nesse intervalo. É especialmente útil quando não sabemos o tamanho do array ou quando o elemento está próximo do início. ## Como Funciona 1. Se o primeiro elemento é o alvo, retorne posição 0 2. Encontre o intervalo: comece com i=1 e dobre até `items[i] > alvo` ou ultrapassar o array 3. Aplique busca binária no intervalo `[i/2, min(i, n-1)]` ### Visualização do Processo ``` Array: [2, 3, 4, 10, 14, 20, 40, 50, 60, 70, 80, 100] Procurando: 40 Fase 1 — Busca Exponencial (encontrar intervalo): i=1: items[1]=3 < 40 → continua i=2: items[2]=4 < 40 → continua i=4: items[4]=14 < 40 → continua i=8: items[8]=60 > 40 → intervalo encontrado! [4, 8] Fase 2 — Busca Binária em [4, 8]: meio=6: items[6]=40 = 40 ✓ Encontrado na posição 6! ``` ## Implementação em Zig ```zig const std = @import("std"); /// Busca exponencial genérica em array ordenado. /// Retorna o índice do elemento ou null. pub fn buscaExponencial(comptime T: type, items: []const T, alvo: T) ?usize { if (items.len == 0) return null; // Caso especial: primeiro elemento if (items[0] == alvo) return 0; // Fase 1: encontrar o intervalo dobrando o índice var i: usize = 1; while (i < items.len and items[i] <= alvo) { i *= 2; } // Fase 2: busca binária no intervalo [i/2, min(i, n-1)] const esquerda = i / 2; const direita = @min(i, items.len - 1); return buscaBinaria(T, items, alvo, esquerda, direita); } /// Busca binária auxiliar no intervalo [esquerda, direita]. fn buscaBinaria( comptime T: type, items: []const T, alvo: T, esq: usize, dir: usize, ) ?usize { var esquerda = esq; var direita = dir; while (esquerda <= direita) { const meio = esquerda + (direita - esquerda) / 2; if (items[meio] == alvo) return meio; if (items[meio] < alvo) { esquerda = meio + 1; } else { if (meio == 0) break; direita = meio - 1; } } return null; } /// Busca exponencial para streams/iteradores onde o tamanho é desconhecido. /// Usa uma função de acesso que retorna null se o índice for inválido. pub fn buscaExponencialStream( comptime T: type, comptime acessar: fn (usize) ?T, alvo: T, ) ?usize { // Verifica o primeiro elemento if (acessar(0)) |primeiro| { if (primeiro == alvo) return 0; } else { return null; } // Encontra o intervalo var i: usize = 1; while (acessar(i)) |valor| { if (valor > alvo) break; if (valor == alvo) return i; i *= 2; } // Busca binária no intervalo, com verificação de limites var esquerda = i / 2; var direita = i; while (esquerda <= direita) { const meio = esquerda + (direita - esquerda) / 2; if (acessar(meio)) |valor| { if (valor == alvo) return meio; if (valor < alvo) { esquerda = meio + 1; } else { if (meio == 0) break; direita = meio - 1; } } else { // Ultrapassou o fim — ajusta direita if (meio == 0) break; direita = meio - 1; } } return null; } pub fn main() !void { const stdout = std.io.getStdOut().writer(); const dados = [_]i32{ 2, 3, 4, 10, 14, 20, 40, 50, 60, 70, 80, 100 }; const alvos = [_]i32{ 40, 2, 100, 15 }; for (alvos) |alvo| { if (buscaExponencial(i32, &dados, alvo)) |idx| { try stdout.print("{d} encontrado na posição {d}\n", .{ alvo, idx }); } else { try stdout.print("{d} não encontrado\n", .{alvo}); } } // Exemplo com stream simulado const stream_data = [_]i32{ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 }; const resultado = buscaExponencialStream(i32, struct { fn f(i: usize) ?i32 { if (i < stream_data.len) return stream_data[i]; return null; } }.f, 13); if (resultado) |idx| { try stdout.print("13 no stream: posição {d}\n", .{idx}); } } ``` ## Análise de Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | **Melhor caso** | O(1) — elemento no início | O(1) | | **Caso médio** | O(log n) | O(1) | | **Pior caso** | O(log n) | O(1) | ### Detalhamento - **Fase exponencial**: O(log i) onde i é a posição do elemento - **Fase binária**: O(log i) no intervalo [i/2, i] - **Total**: O(log i) que no pior caso é O(log n) ### Vantagem para Elementos Próximos ao Início Se o elemento está na posição i, a busca exponencial faz O(log i) comparações. Se i << n, isso é muito melhor que O(log n) da busca binária! ## Quando Usar - **Tamanho desconhecido**: arrays ilimitados ou streams - **Elementos frequentemente próximos ao início**: acesso proporcional à posição - **Arrays muito grandes**: como passo inicial antes da busca binária ## Recursos Relacionados - [Busca Binária em Zig](/algoritmos/busca-binaria/) — Sub-rotina usada pela busca exponencial - [Busca por Interpolação](/algoritmos/busca-interpolacao/) — Alternativa para dados uniformes - [Busca Linear em Zig](/algoritmos/busca-linear/) — Para dados não ordenados - [Busca Ternária em Zig](/algoritmos/busca-ternaria/) — Para funções unimodais - [Array Dinâmico](/estruturas-dados/array-dinamico/) — Estrutura com tamanho variável