Ternary Search

A ternary search algorithm is for finding the minimum or maximum of a unimodal function.

Let $f (x)$ be a unimodal function on some interval $[l, r]$ . Take any two points $m_{1}$ and $m_{2}$ in this segment $l < m_{1} < m_{2} < r$ . Then,

if $f (m_{1}) < f (m_{2})$ , then the required maximum can not be located on the left side, and we need to look only in the interval $[m_{1}, r]$
if $f (m_{1}) > f (m_{2})$ , similarly we need to pay attention to the segment $[l, m_{2}]$
if $f (m_{1}) = f (m_{2})$ , then the search should be conducted in $[m_{1}, m_{2}]$

If we chose points $m_{1}, m_{2}$ as

m_{1} = l + \frac{r - l}{3}, m_{2} = r - \frac{r - l}{3}

then the time complexity of this algorithm is $O (lo g n)$

Lin's Notes Garden

Explorer

Ternary Search

Graph View

Backlinks