Busca em array:
  [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
   esq              m1    m2         dir
   0                3     6          9

Função unimodal (encontrar máximo):
       *
      * *
     *   *
    *     *
   *       *
  esq m1 m2 dir
  Se f(m1) < f(m2), o pico está à direita de m1

const std = @import("std");

/// Busca ternária em array ordenado.
pub fn buscaTernaria(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 terco = (direita - esquerda) / 3;
        const m1 = esquerda + terco;
        const m2 = direita - terco;

        if (items[m1] == alvo) return m1;
        if (items[m2] == alvo) return m2;

        if (alvo < items[m1]) {
            // Alvo está no primeiro terço
            if (m1 == 0) break;
            direita = m1 - 1;
        } else if (alvo > items[m2]) {
            // Alvo está no último terço
            esquerda = m2 + 1;
        } else {
            // Alvo está no terço do meio
            esquerda = m1 + 1;
            if (m2 == 0) break;
            direita = m2 - 1;
        }
    }

    return null;
}

/// Busca ternária para encontrar o MÁXIMO de uma função unimodal.
/// A função deve ter exatamente um máximo no intervalo [esq, dir].
pub fn maximoUnimodal(
    comptime f: fn (f64) f64,
    esq: f64,
    dir: f64,
    epsilon: f64,
) f64 {
    var a = esq;
    var b = dir;

    while (b - a > epsilon) {
        const terco = (b - a) / 3.0;
        const m1 = a + terco;
        const m2 = b - terco;

        if (f(m1) < f(m2)) {
            a = m1;
        } else {
            b = m2;
        }
    }

    return (a + b) / 2.0;
}

/// Busca ternária para encontrar o MÍNIMO de uma função unimodal.
pub fn minimoUnimodal(
    comptime f: fn (f64) f64,
    esq: f64,
    dir: f64,
    epsilon: f64,
) f64 {
    var a = esq;
    var b = dir;

    while (b - a > epsilon) {
        const terco = (b - a) / 3.0;
        const m1 = a + terco;
        const m2 = b - terco;

        if (f(m1) > f(m2)) {
            a = m1;
        } else {
            b = m2;
        }
    }

    return (a + b) / 2.0;
}

/// Busca ternária discreta — encontra o índice do máximo em um
/// array unimodal (cresce e depois decresce).
pub fn maximoArrayUnimodal(items: []const f64) ?usize {
    if (items.len == 0) return null;
    if (items.len == 1) return 0;

    var esquerda: usize = 0;
    var direita: usize = items.len - 1;

    while (direita - esquerda > 2) {
        const terco = (direita - esquerda) / 3;
        const m1 = esquerda + terco;
        const m2 = direita - terco;

        if (items[m1] < items[m2]) {
            esquerda = m1;
        } else {
            direita = m2;
        }
    }

    // Encontra o máximo no intervalo restante
    var max_idx = esquerda;
    var i = esquerda + 1;
    while (i <= direita) : (i += 1) {
        if (items[i] > items[max_idx]) max_idx = i;
    }
    return max_idx;
}

// Funções de exemplo
fn parabolaInvertida(x: f64) f64 {
    // Máximo em x = 3
    return -(x - 3.0) * (x - 3.0) + 9.0;
}

fn funcaoQuadratica(x: f64) f64 {
    // Mínimo em x = 2
    return (x - 2.0) * (x - 2.0) + 1.0;
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    // Busca em array ordenado
    const nums = [_]i32{ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
    if (buscaTernaria(i32, &nums, 11)) |idx| {
        try stdout.print("11 encontrado na posição {d}\n", .{idx});
    }

    // Encontrar máximo de função unimodal
    const x_max = maximoUnimodal(parabolaInvertida, 0.0, 6.0, 1e-9);
    try stdout.print("Máximo de -(x-3)²+9 em x = {d:.6}\n", .{x_max});
    try stdout.print("f(x_max) = {d:.6}\n", .{parabolaInvertida(x_max)});

    // Encontrar mínimo
    const x_min = minimoUnimodal(funcaoQuadratica, -5.0, 10.0, 1e-9);
    try stdout.print("Mínimo de (x-2)²+1 em x = {d:.6}\n", .{x_min});

    // Array unimodal
    const unimodal = [_]f64{ 1, 4, 8, 15, 20, 18, 12, 7, 3 };
    if (maximoArrayUnimodal(&unimodal)) |idx| {
        try stdout.print("Máximo do array unimodal: posição {d}, valor {d}\n", .{ idx, unimodal[idx] });
    }
}