How to recursively search the maximum in a list

Question

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

Possible duplicate of [Finding the maximum element with a recursive function](https://stackoverflow.com/questions/38525085/finding-the-maximum-element-with-a-recursive-function) — Raman Mishra, Nov 03 '18 at 09:23
@RamanMishra Not exactly since the nature of the array is different and he needs in O(log(n)). — nice_dev, Nov 03 '18 at 09:47

score 4 · Accepted Answer · answered Nov 03 '18 at 09:32

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(log₃N). 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

Thanks this is a quite new but useful concept to me! – Alex Wang Nov 03 '18 at 10:52 — Alex Wang, Nov 03 '18 at 10:52

score 1 · Answer 2 · answered Nov 03 '18 at 10:17

Algorithm

You can use binary search to do this(if you wish to).
If we come across a pattern of b-1 < b < b+1 where b was our middle element, then surely the highest element is to the right side of the array.
If we come across a pattern of b-1 > b > b+1 where b was our middle element, then surely the highest element is to the left side of the array.
If we come across a pattern of b-1 < b > b+1 where b was our middle element, then this b is our answer.

CODE:

mid = 0,low=0,high = arr.size-1
while low <= high: 
    mid = low + (high - low) / 2
    if arr[mid] > arr[mid-1] && arr[mid] > arr[mid + 1]:
        return arr[mid]
    else if arr[mid] < arr[mid-1] && arr[mid] > arr[mid + 1]:
        high = mid - 1
    else 
        low = mid + 1

Time complexity is O(log₂n). But, as mentioned by @nellex in his answer, ternary search provides a better performance.

Sorry for the fact that it isn't recursive though – nice_dev Nov 03 '18 at 10:32 — nice_dev, Nov 03 '18 at 10:32

score 0 · Answer 3 · answered Nov 03 '18 at 09:33

The recursive version of your code would be

def max_modal(list, start=0):
    If start < len(list):
        If list[start]>list[start+1]:
            Return list[start]
        Else:
            Return max_modal(list,start=start+1)
     Else:
         Return list[start]

However in a interpreter language this Schild be a lot slower than the iterative way

How to recursively search the maximum in a list

3 Answers3