# How To Recursively Search The Maximum In A List

## 03 November 2018 - 1 answer

I'm quite new to python and algorithm and I encountered a question which is defined as follows:

Suppose that you are given a python list `l` of size `n` which contains only numbers. We index `l` from 0 to `n-1`. Further, we suppose that there exists an index `k ∈ {1, ..., n-2}` such that

• for all `i ∈ {0, ..., k-1}`, `l[i] < l[i+1]`
• for all `i ∈ {k, ..., n-2}`, `l[i] > l[i+1]`

In other words, l is unimodal. An example with `k=3` is given below:

l = [-5, 8, 12, 15, 13, 12, 10, 5, 1, 0, -2]

I can easily implement it using an iterative approach:

``````def findK(l):
k = 0
while l[k] < l[k + 1]:
k += 1
return k
``````

But how can I do it using a recursive way which is O(logn)?

The maximum/minimum of a unimodal function can be obtained by using the concept of Ternary Search

``````def ternarySearch(f, left, right, absolutePrecision):
'''
left and right are the current bounds;
the maximum is between them
'''
if abs(right - left) < absolutePrecision:
return (left + right)/2

leftThird = (2*left + right)/3
rightThird = (left + 2*right)/3

if f(leftThird) < f(rightThird):
return ternarySearch(f, leftThird, right, absolutePrecision)
else:
return ternarySearch(f, left, rightThird, absolutePrecision)
``````

The overall complexity of the solution is O(log3N). You can learn more about it from https://www.hackerearth.com/practice/algorithms/searching/ternary-search/tutorial/ or https://en.wikipedia.org/wiki/Ternary_search