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!

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