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

Linear Scan

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.

Code

def findPeakNaive(array, n):
  
  if n==1: #if array only contains one element
    return array[0]

  if array[0] >= array[1]: #if first element is a peak
    return array[0]

  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)

Output

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.

Code

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)

Output

The peak is: 6