Find Peak Element in Python

A peak element in an array is defined as an element that is greater than its neighbors. We can use some common approaches such as binary search to efficiently locate a peak element and linear search algorithm which involves iterating through an array.

Binary Search Approach

The Binary Search is an efficient technique for locating a peak element in an array. To find a peak, follow these steps:

• Choose the middle element of the array.

• If it's greater than or equal to the left neighbor, search the right half (including the middle). If it's smaller, search the left half.

• Repeat this process until a peak is found.

Steps include finding one of the peak elements in the array using a binary search approach.

• Class Initialization

• Binary search loop

• Return Peak Element Index

Class Initialization

Consider an array, Initialize two pointers: low at the start of the array (index 0) and high at the end of the array (index n-1, where n is the length of the array).

class Solution(object): def findPeakElement(self, nums): low = 0 high = len(nums) - 1 

Binary Search loop

Use a loop that continues until the low pointer is less than the high pointer. Inside the loop:

• Calculate the mid-point index using mid = low + (high - low + 1) // 2. Check if the middle element is greater than or equal to its left neighbor.
• If true, set low to mid, indicating a peak may be to the right (or at mid). If false, set high to mid-1, indicating a peak must be to the left.

Observe the following snippet -

while low < high: mid = low + (high - low + 1) // 2 # Check if mid is greater than or equal to its left neighbor if mid - 1 >= 0 and nums[mid - 1] <= nums[mid]: low = mid else: high = mid - 1 

Return Peak Element Index

Once the loop exits, the low will point to a peak element. Return the index of this peak.

return low 

Example

Here's a demonstration using an example array.

class Solution(object): def findPeakElement(self, nums): low = 0 high = len(nums) - 1 while low < high: mid = low + (high - low + 1) // 2 # Check if mid is greater than or equal to its left neighbor if mid - 1 >= 0 and nums[mid - 1] <= nums[mid]: low = mid else: high = mid - 1 return low ob1 = Solution() result = ob1.findPeakElement([15, 35, 85, 96, 5, 6, 8, 12]) print('The Index of Peak Element is :',result) 

Following the output for the above code-

The Index of Peak Element is : 3 

 Linear Search Approach

In this approach, we iterate through the array to identify a peak element. This method has a time complexity of O(n).

The steps involved in finding the peak in an array using linear search are as follows.

• Class Initialization

• Linear search loop

• Return Peak Element Index

Class Initialization

Start by defining a class. Initialize a loop to traverse the array from the first to the last element.

class Solution(object): def findPeakElement(self, nums): n = len(nums) for i in range(n): 

Linear Search loop

Checking each element, If the current element is greater than or equal to its neighbours (if they exist), it is a peak. Return its index.

if (i == 0 or nums[i] >= nums[i - 1]) and (i == n - 1 or nums[i] >= nums[i + 1]): return i 

Return Peak Element Index

If no peak is found during the traversal, the first or last element can also be considered a peak, and you can return its index.

return 0 

Example

Here's a demonstration using an example array:

class Solution(object): def findPeakElement(self, nums): n = len(nums) for i in range(n): # Check if the current element is greater than its neighbors if (i == 0 or nums[i] >= nums[i - 1]) and (i == n - 1 or nums[i] >= nums[i + 1]): return i return 0 # This line will never be reached in a valid input ob2 = Solution() result = ob2.findPeakElement([15, 35, 85, 96, 5, 6, 8, 12]) print('The Index of Peak Element is :', result) 

Following is the output for the above code-

The Index of Peak Element is : 3