How to use ternary search
Short description
In practice, functions which first decrease and then increase (or vice versa) occur frequently. Then, one can use ternary search to find the optimal value.
Prerequisites
Perhaps basic familiarity with binary search would be useful.
Long description
General idea. There are a lot of unimodal functions (these are functions which first increase and then decrease or vice versa) especially of the geometrical flavour. In that case, one can use ternary search in order to find the extremum. One can think about the suitable functions in the following way: if the argument of our function is very large (or very small) then the value is bad, because "it's far". And when we move our argument closer to the optimal one, the value constantly improves. For most functions it is more or less easy to prove rigorously after some technical efforts.
Speed up. If one know the general scheme of ternary search algorithm, they won't be surprised that we can choose arbitrary points to proceed, now just at the thirds. For instance, the segment ratio like
Multidimensional ternary search. See here.
What follows is a sheaf of examples.
Example 1
Town X is in the point
Explanation.
In any way we need to intersect the line
This function is clearly unimodal, hence we can use ternary search to find the optimal
Example 2
There are
Explanation.
Given a fixed
Example 3
(One can imagine towers of boxes in the following problem.) Given an array
-
choose
and increase by one, -
choose
such that and decrease it by one.
Find the minimal value of operations needed to make at least
Explanation.
Let
Example 4
There are
Explanation.
Perform ternary search of