Ternary Search

#include<bits/stdc++.h>
#define ll long long

pair<ll, ll> ternary_search(ll l, ll r) {
    // change the below get_f function to your desired function.
    // by default, it finds x, f(x) in [l, r] so that f(x) = 2x^2 - 12x + 7 MIN.
    auto get_f = [](ll x) {
        return 2*x*x - 12*x + 7;
    };
    
    while(l < r-2) {
        ll mid1 = l + (r-l)/3;
        ll mid2 = l + 2*(r-l)/3;
        
        ll f1 = get_f(mid1);
        ll f2 = get_f(mid2);
        
        if (f1 < f2)
            r = mid2;
        else
            l = mid1;
    }
    
    ll best_value = get_f(l);
    ll best_x = l;
    for (ll i = l+1; i <= r; ++i)
        if (get_f(i) < best_value) {
            best_value = get_f(i);
            best_x = i;
        }
    
    return make_pair(best_x, best_value);
}