Ad

How To Recursively Search The Maximum In A List

- 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)?

Ad

Answer

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

Ad
source: stackoverflow.com
Ad