--- title: "Como Fazer Busca Binária em Zig" url: "https://ziglang.com.br/receitas/como-fazer-busca-bin%C3%A1ria-em-zig/" markdown_url: "https://ziglang.com.br/receitas/como-fazer-busca-bin%C3%A1ria-em-zig.MD" description: "Aprenda a implementar busca binária em Zig para encontrar elementos de forma eficiente em arrays ordenados. Exemplos com tipos primitivos e structs." date: "2026-02-21" author: "Zig Brasil" --- # Como Fazer Busca Binária em Zig Aprenda a implementar busca binária em Zig para encontrar elementos de forma eficiente em arrays ordenados. Exemplos com tipos primitivos e structs. ## Introdução A busca binária é um algoritmo eficiente que encontra elementos em arrays ordenados com complexidade O(log n). Em vez de verificar cada elemento, ela divide o espaço de busca pela metade a cada passo. A biblioteca padrão do Zig oferece `std.sort.binarySearch` pronto para uso. Nesta receita, você aprenderá a usar busca binária tanto com a implementação padrão quanto com implementações customizadas. ## Pré-requisitos - Zig instalado (versão 0.13+). Veja o [guia de instalação](/tutoriais/como-instalar-zig/) - Conhecimento básico de Zig. Consulte a [introdução ao Zig](/tutoriais/introducao-ao-zig/) ## Busca Binária Básica Buscar um valor em um array ordenado de inteiros: ```zig const std = @import("std"); pub fn main() !void { const numeros = [_]i32{ 2, 5, 8, 12, 16, 23, 38, 42, 56, 72, 91 }; // Buscar usando std.sort.binarySearch const alvo: i32 = 23; const resultado = std.sort.binarySearch(i32, alvo, &numeros, {}, struct { fn compare(_: void, key: i32, item: i32) std.math.Order { return std.math.order(key, item); } }.compare); if (resultado) |idx| { std.debug.print("Valor {d} encontrado no índice {d}\n", .{ alvo, idx }); } else { std.debug.print("Valor {d} não encontrado\n", .{alvo}); } // Buscar valor inexistente const nao_existe: i32 = 25; const r2 = std.sort.binarySearch(i32, nao_existe, &numeros, {}, struct { fn compare(_: void, key: i32, item: i32) std.math.Order { return std.math.order(key, item); } }.compare); if (r2) |idx| { std.debug.print("Valor {d} encontrado no índice {d}\n", .{ nao_existe, idx }); } else { std.debug.print("Valor {d} não encontrado\n", .{nao_existe}); } } ``` ### Saída esperada ``` Valor 23 encontrado no índice 5 Valor 25 não encontrado ``` ## Implementação Manual de Busca Binária Para entender o algoritmo e ter mais controle: ```zig const std = @import("std"); fn buscaBinaria(comptime T: type, arr: []const T, alvo: T) ?usize { if (arr.len == 0) return null; var esquerda: usize = 0; var direita: usize = arr.len - 1; while (esquerda <= direita) { const meio = esquerda + (direita - esquerda) / 2; if (arr[meio] == alvo) { return meio; } else if (arr[meio] < alvo) { if (meio == arr.len - 1) break; esquerda = meio + 1; } else { if (meio == 0) break; direita = meio - 1; } } return null; } pub fn main() !void { const dados = [_]u32{ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 }; const testes = [_]u32{ 30, 75, 100, 10, 55 }; for (&testes) |alvo| { if (buscaBinaria(u32, &dados, alvo)) |idx| { std.debug.print("{d} encontrado no índice {d}\n", .{ alvo, idx }); } else { std.debug.print("{d} não encontrado\n", .{alvo}); } } } ``` ## Busca Binária em Structs Buscar em uma lista ordenada de structs: ```zig const std = @import("std"); const Produto = struct { codigo: u32, nome: []const u8, preco: f64, }; pub fn main() !void { // Array deve estar ordenado pelo campo de busca (codigo) const catalogo = [_]Produto{ .{ .codigo = 101, .nome = "Mouse", .preco = 89.90 }, .{ .codigo = 205, .nome = "Teclado", .preco = 199.90 }, .{ .codigo = 310, .nome = "Monitor", .preco = 1299.00 }, .{ .codigo = 422, .nome = "Headset", .preco = 349.90 }, .{ .codigo = 538, .nome = "Webcam", .preco = 459.00 }, }; const codigo_busca: u32 = 310; const resultado = std.sort.binarySearch(Produto, codigo_busca, &catalogo, {}, struct { fn compare(_: void, key: u32, item: Produto) std.math.Order { return std.math.order(key, item.codigo); } }.compare); if (resultado) |idx| { const p = catalogo[idx]; std.debug.print("Produto encontrado:\n", .{}); std.debug.print(" Código: {d}\n", .{p.codigo}); std.debug.print(" Nome: {s}\n", .{p.nome}); std.debug.print(" Preço: R$ {d:.2}\n", .{p.preco}); } else { std.debug.print("Produto com código {d} não encontrado\n", .{codigo_busca}); } } ``` ## Encontrar Ponto de Inserção Encontrar onde um elemento deveria ser inserido para manter a ordenação: ```zig const std = @import("std"); fn pontoDeInsercao(comptime T: type, arr: []const T, alvo: T) usize { var esquerda: usize = 0; var direita: usize = arr.len; while (esquerda < direita) { const meio = esquerda + (direita - esquerda) / 2; if (arr[meio] < alvo) { esquerda = meio + 1; } else { direita = meio; } } return esquerda; } pub fn main() !void { const ordenado = [_]i32{ 10, 20, 30, 40, 50 }; const valores = [_]i32{ 5, 15, 25, 35, 45, 55 }; for (&valores) |v| { const pos = pontoDeInsercao(i32, &ordenado, v); std.debug.print("{d} seria inserido na posição {d}\n", .{ v, pos }); } } ``` ### Saída esperada ``` 5 seria inserido na posição 0 15 seria inserido na posição 1 25 seria inserido na posição 2 35 seria inserido na posição 3 45 seria inserido na posição 4 55 seria inserido na posição 5 ``` ## Busca Binária em Floats ```zig const std = @import("std"); pub fn main() !void { const temperaturas = [_]f64{ -10.5, -3.2, 0.0, 5.7, 12.3, 18.9, 25.4, 31.1, 37.8 }; const alvo: f64 = 18.9; const resultado = std.sort.binarySearch(f64, alvo, &temperaturas, {}, struct { fn compare(_: void, key: f64, item: f64) std.math.Order { return std.math.order(key, item); } }.compare); if (resultado) |idx| { std.debug.print("Temperatura {d:.1}°C encontrada no índice {d}\n", .{ alvo, idx }); } else { std.debug.print("Temperatura {d:.1}°C não encontrada\n", .{alvo}); } } ``` ## Dicas e Boas Práticas 1. **O array DEVE estar ordenado**: Busca binária só funciona em dados ordenados. Use [std.mem.sort](/receitas/zig-ordenar-array/) antes se necessário. 2. **Complexidade O(log n)**: Para 1 milhão de elementos, busca binária precisa de apenas ~20 comparações. 3. **Use `std.sort.binarySearch`**: A implementação padrão é testada e otimizada. Só implemente manualmente se precisar de comportamento especial. 4. **Cuidado com overflow**: Na implementação manual, use `esquerda + (direita - esquerda) / 2` em vez de `(esquerda + direita) / 2` para evitar overflow. ## Receitas Relacionadas - [Ordenar Arrays e Slices](/receitas/zig-ordenar-array/) - Preparar dados para busca - [Arrays Dinâmicos com ArrayList](/receitas/zig-arraylist-dinamico/) - Listas dinâmicas - [Como usar HashMap em Zig](/receitas/zig-hashmap-uso/) - Alternativa com O(1) - [Filtrar Arrays](/receitas/zig-filtrar-array/) - Filtrar resultados ## Tutoriais Relacionados - [Introdução ao Zig](/tutoriais/introducao-ao-zig/) - [Structs, Enums e Unions em Zig](/tutoriais/structs-enums-unions-zig/)