The problem of finding a peak element in an array involves looking for an item that is not smaller than its neighbors. If an element is at the boundary, i.e., either at index 0 or n-1, we need to compare it with only one neighbor. Otherwise, we need to compare it with two neighbors, i.e., items at the right and left.
Moreover, there can be more than one peak in an array, but we only need to find one.
Consider the following example.
Data = 4, 2, 5, 6, 3, 7, 8 Peak = 4 at index 0 Peak = 6 at index 3 Peak = 8 at index 6
We can solve this problem by doing a linear scan of the array and compare each element with its neighbors. This approach will include three cases.
- If the element is at index 0, then we need to check if it is greater than or equal to the item at index 1.
- If the element is at index n-1, then we compare it with the item at index n-2.
- Otherwise, we traverse from index 1 to n-2. We compare the element present at index i with items at index i-1 and i+1. If the peak is found, we return it. Else, the search continues.
def findPeakNaive(array, n): if n==1: #if array only contains one element return array if array >= array: #if first element is a peak return array elif array[n-1] >= array[n-2]: #if last element is a peak return array[n-1] else: for i in range(1, n-1): if ((array[i] >= array[i-1]) and (array[i] >= array[i+1])): return array[i] array = [1, 2, 5, 6, 3, 7, 3] peak = findPeakNaive(array, len(array)) print("The peak is:", peak)
The peak is: 6
However, this approach is naïve, and it has a time complexity of
O(n) in the worst case.
Recursive Binary Search
This can be a better approach because we only need a single peek. Therefore, there is no need to scan the whole array. We do it by using the divide and conquer approach. It will provide us a time complexity of
O(logn). This approach is similar to the binary search. We find the middle element and check if it is the peak. If it is, we return it. Otherwise, we see if the next item is greater than the peak. If that is true, then a peak lies on the right side of the middle value. Therefore, we recurse for that part. If the item before the middle element is greater, we recurse for the left side because a peak lies there.
def findPeak(array, l, r, n): mid = l + (r-l)//2 if (( mid == 0 or array[mid] >= array[mid-1]) and (mid == n-1 or array[mid] >= array[mid+1])): #check if middle element is a peak return array[mid] elif (array[mid+1]>array[mid]): #recurse for the right if the array[mid+1] is greater than the middle element return findPeak(array, mid+1, r, n) else: #recurse for the left side if the array[mid-1] is greater than the middle element return findPeak(array, l, mid-1, n) array = [1, 2, 5, 6, 3, 7, 3] peak = findPeak(array, 0, len(array)-1, len(array)) print("The peak is:", peak)
The peak is: 6