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)

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});
    }
}