Ternary Search
(algo/search/ternary_search.hpp)

• View this file on GitHub
• Last update: 2026-07-07 22:10:04+09:00
• Include: #include "algo/search/ternary_search.hpp"

Overview

Ternary-search helpers find an argument of a unimodal function. Integer functions search a half-open range [left, right) and return the smallest optimal argument. Real functions search a closed interval approximately and return the midpoint of the final interval.

The public namespace is m1une::algo.

Functions

Function	Description	Complexity
ternary_search_argmin(left, right, f)	Returns an integer argument minimizing f on [left, right).	$O(\log N)$ evaluations
ternary_search_argmax(left, right, f)	Returns an integer argument maximizing f on [left, right).	$O(\log N)$ evaluations
real_ternary_search_argmin(left, right, f, iterations = 100)	Returns an approximate real minimizer.	$O(\text{iterations})$ evaluations
real_ternary_search_argmax(left, right, f, iterations = 100)	Returns an approximate real maximizer.	$O(\text{iterations})$ evaluations

The integer range must be nonempty. The function must be unimodal in the requested direction.

Example

#include "algo/search/ternary_search.hpp"

#include <iostream>

int main() {
    auto f = [](long long x) {
        return (x - 7) * (x - 7) + 3;
    };
    long long x = m1une::algo::ternary_search_argmin<long long>(-100, 101, f);
    std::cout << x << '\n';
}

Required by

• Algorithms All (algo/all.hpp)
• Search Algorithms All (algo/search/all.hpp)

Verified with

• verify/algo/search/ternary_search.test.cpp

Code

#ifndef M1UNE_ALGO_SEARCH_TERNARY_SEARCH_HPP
#define M1UNE_ALGO_SEARCH_TERNARY_SEARCH_HPP 1

#include <cassert>
#include <concepts>

namespace m1une {
namespace algo {

template <std::integral Int, class F>
Int ternary_search_argmin(Int left, Int right, F f) {
    assert(left < right);
    while (right - left > 3) {
        const Int third = (right - left) / 3;
        const Int middle_left = left + third;
        const Int middle_right = right - third;
        if (f(middle_right) < f(middle_left)) {
            left = middle_left + 1;
        } else {
            right = middle_right;
        }
    }

    Int best = left;
    auto best_value = f(best);
    for (Int x = left + 1; x < right; ++x) {
        auto value = f(x);
        if (value < best_value) {
            best = x;
            best_value = value;
        }
    }
    return best;
}

template <std::integral Int, class F>
Int ternary_search_argmax(Int left, Int right, F f) {
    assert(left < right);
    while (right - left > 3) {
        const Int third = (right - left) / 3;
        const Int middle_left = left + third;
        const Int middle_right = right - third;
        if (f(middle_left) < f(middle_right)) {
            left = middle_left + 1;
        } else {
            right = middle_right;
        }
    }

    Int best = left;
    auto best_value = f(best);
    for (Int x = left + 1; x < right; ++x) {
        auto value = f(x);
        if (best_value < value) {
            best = x;
            best_value = value;
        }
    }
    return best;
}

template <class F>
double real_ternary_search_argmin(double left, double right, F f, int iterations = 100) {
    assert(left <= right);
    assert(0 <= iterations);
    for (int i = 0; i < iterations; ++i) {
        const double middle_left = (left * 2.0 + right) / 3.0;
        const double middle_right = (left + right * 2.0) / 3.0;
        if (f(middle_right) < f(middle_left)) {
            left = middle_left;
        } else {
            right = middle_right;
        }
    }
    return (left + right) / 2.0;
}

template <class F>
double real_ternary_search_argmax(double left, double right, F f, int iterations = 100) {
    assert(left <= right);
    assert(0 <= iterations);
    for (int i = 0; i < iterations; ++i) {
        const double middle_left = (left * 2.0 + right) / 3.0;
        const double middle_right = (left + right * 2.0) / 3.0;
        if (f(middle_left) < f(middle_right)) {
            left = middle_left;
        } else {
            right = middle_right;
        }
    }
    return (left + right) / 2.0;
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_SEARCH_TERNARY_SEARCH_HPP

#line 1 "algo/search/ternary_search.hpp"



#include <cassert>
#include <concepts>

namespace m1une {
namespace algo {

template <std::integral Int, class F>
Int ternary_search_argmin(Int left, Int right, F f) {
    assert(left < right);
    while (right - left > 3) {
        const Int third = (right - left) / 3;
        const Int middle_left = left + third;
        const Int middle_right = right - third;
        if (f(middle_right) < f(middle_left)) {
            left = middle_left + 1;
        } else {
            right = middle_right;
        }
    }

    Int best = left;
    auto best_value = f(best);
    for (Int x = left + 1; x < right; ++x) {
        auto value = f(x);
        if (value < best_value) {
            best = x;
            best_value = value;
        }
    }
    return best;
}

template <std::integral Int, class F>
Int ternary_search_argmax(Int left, Int right, F f) {
    assert(left < right);
    while (right - left > 3) {
        const Int third = (right - left) / 3;
        const Int middle_left = left + third;
        const Int middle_right = right - third;
        if (f(middle_left) < f(middle_right)) {
            left = middle_left + 1;
        } else {
            right = middle_right;
        }
    }

    Int best = left;
    auto best_value = f(best);
    for (Int x = left + 1; x < right; ++x) {
        auto value = f(x);
        if (best_value < value) {
            best = x;
            best_value = value;
        }
    }
    return best;
}

template <class F>
double real_ternary_search_argmin(double left, double right, F f, int iterations = 100) {
    assert(left <= right);
    assert(0 <= iterations);
    for (int i = 0; i < iterations; ++i) {
        const double middle_left = (left * 2.0 + right) / 3.0;
        const double middle_right = (left + right * 2.0) / 3.0;
        if (f(middle_right) < f(middle_left)) {
            left = middle_left;
        } else {
            right = middle_right;
        }
    }
    return (left + right) / 2.0;
}

template <class F>
double real_ternary_search_argmax(double left, double right, F f, int iterations = 100) {
    assert(left <= right);
    assert(0 <= iterations);
    for (int i = 0; i < iterations; ++i) {
        const double middle_left = (left * 2.0 + right) / 3.0;
        const double middle_right = (left + right * 2.0) / 3.0;
        if (f(middle_left) < f(middle_right)) {
            left = middle_left;
        } else {
            right = middle_right;
        }
    }
    return (left + right) / 2.0;
}

}  // namespace algo
}  // namespace m1une

Back to top page