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
- Conhecimento básico de Zig. Consulte a introdução ao Zig
Busca Binária Básica
Buscar um valor em um array ordenado de inteiros:
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:
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:
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:
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
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
O array DEVE estar ordenado: Busca binária só funciona em dados ordenados. Use std.mem.sort antes se necessário.
Complexidade O(log n): Para 1 milhão de elementos, busca binária precisa de apenas ~20 comparações.
Use
std.sort.binarySearch: A implementação padrão é testada e otimizada. Só implemente manualmente se precisar de comportamento especial.Cuidado com overflow: Na implementação manual, use
esquerda + (direita - esquerda) / 2em vez de(esquerda + direita) / 2para evitar overflow.
Receitas Relacionadas
- Ordenar Arrays e Slices - Preparar dados para busca
- Arrays Dinâmicos com ArrayList - Listas dinâmicas
- Como usar HashMap em Zig - Alternativa com O(1)
- Filtrar Arrays - Filtrar resultados