1.1 KiB
A peak in a 1D list of values is a value that is not smaller than its neighbours. Assume all values are natural numbers.
For example, consider the following list of values a = [1, 6, 7, 4, 3, 2, 1, 4, 5, 6]
Here, 7 is a peak and 6 is a peak.
Write a python program that uses recursion to find a peak (not all, just one peak) given a list of values. Your function should return the list index of the peak. To do so you must implement the following recursive algorithm that uses the same idea as binary search (i.e., divide and conquer). •Recursively look at position n//2 •if a[n//2] < a[n//2 - 1] then only look at left half 0 … n//2-1 to look for a peak •else if a[n//2] < a[n//2 + 1] then only look at right half n//2+1 … n-1 to look for a peak •else n//2 position is a peak
Note that although there are two peaks in the given example, this method will only find peak 7 at index 2. Your program must follow this behaviour.
Input specification: • A line with the numbers separated by space
Output specification: • The index of the peak
Sample testcases (The bolded text are user input)
Case 1: 1 6 7 4 3 2 1 4 5 6 2
Case 2: 1 10 2 1