Ternary Search and Search Space Reduction

Ternary search needs a unimodal objective

For optimization, ternary search discards part of an interval by comparing two interior points of a unimodal function. For a minimum, values decrease toward the optimum and increase afterward. Arbitrary functions do not satisfy this requirement.

Copy codefun minimumPoint(left: Double, right: Double, value: (Double) -> Double): Double {
    require(left.isFinite() && right.isFinite() && left <= right)
    var low = left
    var high = right
    repeat(100) {
        val first = low + (high - low) / 3
        val second = high - (high - low) / 3
        if (value(first) < value(second)) high = second else low = first
    }
    return (low + high) / 2
}

This educational version assumes finite evaluations, a unimodal objective, and a reasonably bounded interval where intermediate arithmetic remains finite. A fixed iteration count avoids floating-point termination traps. Integer-domain variants should finish by checking a small remaining range directly.

Exercise

Minimize (x-3)² on [0,10] and compare the result to three with a tolerance. Try a multi-valley function and explain why the guarantee disappears.

Check: for finding an item in a sorted array, ordinary binary search is usually the appropriate tool; this lesson's main use is unimodal optimization.

Further reading: Searching and invariants