CODEWITHSUNDEEP
pythonalgorithm
Alex Wang
Alex Wang

Reputation: 481

How to recursively search the maximum in a list

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

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

Upvotes: 1

Views: 635

Answers (3)

nice_dev
nice_dev

Reputation: 17805

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(log2n). But, as mentioned by @nellex in his answer, ternary search provides a better performance.

Upvotes: 1

user10596792
user10596792

Reputation:

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

Upvotes: 0

Nilesh
Nilesh

Reputation: 1343

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

Upvotes: 4

Related Questions