Ternary Search Algorithm: Explained with example.

The ternary search algorithm is a fast searching algorithm for finding maximum or minimum of a unimodal function. It is similar to binary search and comes under divide and conquer paradigm. It can also be used to search the maximum value of $f(x)$ in the range $[L, R]$ if unimodal property is satisfied in this range.

What is unimodal function

A function is said to be unimodal if it obeys one of the following properties.

• The function strictly increases first, reaches maximum and then strictly decreases.
• The function strictly decreases first, reaches minimum and then strictly increases.

Visual representation of the Unimodal function (source: GeeksForGeeks)

Example

Problem Statement

Given a unimodal function $f(x) = 6 + x - 0.5x ^2$. Find the maximum value of $f(x)$ for integer $x$ where $-10^9 < x < 10^9$ .

Brute Force Solution

The simple brute force approach for the above problem is to enumerate all the possible values of $x$ from $-10^9$ to $10^9$, calculate the value of $f(x)$ and note down the maximum of all the obtained values of $f(x)$. This looks to be a correct solution, but the time complexity for the above approach is $o(n)$ where $n$ is range of values that $x$ can take. In this case n is of order $2 * 10^9$ which is huge in terms of time complexity.

Efficient approach using Ternary Search

While this problem can also be solved using binary search, lets try to explore solution using ternary search algorithm. The above given function is a quadratic equation and is a unimodal in nature, thus we can apply ternery search on this problem.

Here let me explain working of ternery search. We will start with search space equal to full range $[L, R]$. In each iteration, we will remove one-third of the search space range which will not contain the maximum value. We will do this until the search space exhausts. At the end, we will have our maximum.

Consider our range is denoted by $l$ and $r$. We will find two points $p1$ - represents one third part of range and $p2$ - represents two third part of the range.

$p1 = l + \frac{r - l}{3}$

$p2 = r - \frac{r - l}{3}$

• if $f(p1) < f(p2)$, our maximum cannot be in range $[l, p1]$, so our new range will be $(p1, r]$
• if $f(p1) > f(p2)$, our maximum cannot be in range $[p2, r]$, so our new range will be $[l, p2)$
• if $f(p1) == f(p2)$, our maximum cannot be in range $[l, p1)$ && $(p2, r]$, so our new range will be $[p1, p2]$

Now let's write a python code to implement the above technique and solve the given problem.

# returns the value of f(x)
def f(x):
    return 6 + x - 0.5 * x * x

low = -1e9
high = 1e9
ans_index = None
while low <= high:
    # p1 represents the one-third part of the range
    p1 = low + (high - low) // 3 
    # p2 represents the two third part of the range
    p2 = high - (high - low) // 3
    if f(p1) < f(p2):
        # the final answer can be p2 at this instance, hence update the answer
        ans_index = p2 
        # reduce the search space to (p1, high]
        low = p1 + 1
    else:
        # reduce the search space to [low, p2)
        high = p2 - 1

# Final answer
print(f(ans_index))

Output

The above code prints $6.5$ as the maximum value of $f(x)$ which is the correct answer.

Time Complexity

If the initial length of the range is $n$, after one iteration the remaining length will be $2n/3$. Therefore the Run time equation can be derived as,

$T(n) = T(2n / 3) + 1$

Solving the above equation, we get the time complexity to be $o(log(n))$

Conclusion

The ternary search can be used to solve many problems that involve unimodular behaviour in them. It has a very simple implementation and is very easy to understand.