Find a peak element in a given array in Python

Hello, in this tutorial we will learn how to find the peak element in a given array in python. Now, you must be wondering what is the peak element in an array? can there be more than one peak element in the same array? so, let us learn about these things and our primary approach to find the peak element(s).

Python program to find a peak element in an array

First of all, we must know what are peak elements? Peak elements are those elements that are greater than their neighbors in an array that is it must be greater than the number next to it and previous of it in the array. For example, if we are given an array {20,3,4,8,33,12,11} then “20” and “33” are peak elements because 20>8 and 33>12 and 8 both, which means they are greater then their neighbors. But while coding we return only one peak element so our program can return either 20 or 33.

Now, what should be our primary approach? For a novice, he will take the first element and compare it will the element next to it, decide whether it is peak or not. Again, it will iterate through the array, pick the second element and compare it with its neighbor and so on. Hence, the user will end up iterating through the array ‘N’ times where N is the number of elements in the array, so we can say the time complexity of the primary approach is O(n) which is quite satisfactory.

But what if I say we can yet optimize our approach and reduce the time complexity to O(logN)! seems interesting? Let’s know-how?

 

Find peak elements in an array in time complexity of O(logN):

Here, we will use a popular algorithm known as Divide and Conquer approach. In such an approach, we divide the array into two parts, solve them individually and conquer the shorter problem. Hence when the array is divided into two parts, the time complexity reduces logarithmically. We will use recursion here, we will check for the middle element to be peak element or not. If the middle element is the peak element, we will print it. If not, we will divide the array by middle element and apply recursion on the right and left array. There, Recursion will do its magic and print the peak elements for us automatically.

Now we just leave the primary approach for the viewer to try and Let’s code for our optimized approach.

# Online Python compiler (interpreter) to run Python online.
# Write Python 3 code in this online editor and run it.
def help(Array,startIndex,endIndex,N): 
      
    # Find index of middle element.
    middleIndex = startIndex + (endIndex - startIndex)/2 
    middleIndex = int(middleIndex) 
      
    # Compare middle element with its neighbours (if neighbours exist) 
    if ((middleIndex == 0 or Array[middleIndex - 1] <= Array[middleIndex]) and (middleIndex == N - 1 or Array[middleIndex + 1] <= Array[middleIndex])): 
     return middleIndex
    # If middle element is not peak and left element is greater then apply recursion on left array. 
    elif (middleIndex > 0 and Array[middleIndex - 1] > Array[middleIndex]): 
     return help(Array,startIndex,middleIndex-1,N) 
  
    # else apply recusrion on right array.
    else: 
     return help(Array,middleIndex+1,endIndex,N) 
  
  
# Main recursive function
def findPeak(Array,N): 
    index = help(Array,0,N-1,N)
    return index 
  
  
# Main code 
Array = [20,3,4,8,33,12,11]
N= len(Array)
Output: Peak element in the array is 33

So we have successfully able to find the peak element from the given array in Python.

I hope this tutorial was helpful to you. Thank you for your time.
You can also refer to other tutorials related to python: Rearranging the letters of a string in alphabetical order in Python

Leave a Reply

Your email address will not be published. Required fields are marked *