Ternary Search

Find the maximum of a unimodal function using ternary search.

ternary-search binary-search unimodal search

A discrete function f defined on integer indices is called unimodal if it strictly increases up to some point m, then strictly decreases after m. That is, there exists an index m such that f(i) < f(i+1) for all i < m and f(i) > f(i+1) for all i >= m. The goal is to find an index i (0 <= i < n) such that f(i) equals the maximum value of f.

Write a function `ternary_search(arr)` that takes a list of integers `arr` representing the values of a unimodal function at indices 0..n-1 and returns the index of the maximum value. If there are multiple equal maxima (which can happen if the plateau is at the maximum), return the smallest index among them.

Constraints:
- 1 <= n <= 10^5
- Values can be any integers, but sequence is unimodal (non-decreasing then non-increasing).
- The function should run in O(log n) time.

You may assume the input is unimodal.

Constraints

1 <= len(arr) <= 10^5. The sequence is unimodal (strictly increases then strictly decreases, possibly with a plateau at the maximum).

Example

>>> ternary_search([1,2,3,2,1])
2
>>> ternary_search([1,2,2,2,1])
1
>>> ternary_search([5])
0
>>> ternary_search([0,1,2,3,4])
4

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think about dividing the search space into three parts and comparing values at m1 and m2.

If arr[m1] < arr[m2], then the maximum cannot be to the left of m1, so set lo = m1 + 1. Otherwise, set hi = m2 - 1.

When the search space becomes small, just scan the remaining elements because the plateau might affect the comparison.

Careful with plateau: if arr[m1] == arr[m2], you can still shrink the interval to [m1, m2].

Use a loop until hi - lo > 2, then linearly scan the final small range.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.