Peak element in an array

 Given an array. we should Find a peak element in it. An array element is a peak if it is not smaller than its neighbours. For corner elements, we need to consider only one neighbour.

Example:
Input: array[]= {5, 10, 20, 15}
Output: 20
The element 20 has neighbours 10 and 15,
both of them are less than 20.

Input: array[] = {10, 20, 15, 2, 23, 90, 67}
Output: 20 or 90
The element 20 has neighbours 10 and 15, 
both of them are less than 20, similarly, 90 has neighbour 23 and 67.

method 1:

Naive Approach: The array can be traversed and the element whose neighbours are less than that element can be returned.

1.  the first element is greater than the second or the last element is greater than the second last, than print that particular element
2. Else traverse the array from the second index to the second last index
3. If for an element array[i], it is greater than both its neighbours, i.e., array[i] > array[i-1] and array[i] > array[i+1], then print that element.

f

int peakElement(int arr[], int n)
{
    if (n == 1)  
      return arr[0]; 
    if (arr[0] >= arr[1]) 
        return 0; 
    if (arr[n - 1] >= arr[n - 2]) 
        return n - 1; 
  
    for (int i = 1; i < n - 1; i++) 
{ 
        if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) 
            return i; 
 }   
}

Complexity Analysis:

• Time complexity: O(n).
  
• Space Complexity: O(1).
  
  
  
  

method 2: divide and conquer approach

1. Create two variables, l and r, initilize l = 0 and r = n-1
2. Iterate the steps below till l <= r, lowerbound is less than the upperbound
3. Check if the mid value or index mid = (l+r)/2, is the peak element or not, if yes then print the element and terminate.
4. Else if the element on the left side of the middle element is greater then check for peak element on the left side, i.e. update r = mid – 1
5. Else if the element on the right side of the middle element is greater then check for peak element on the right side, i.e. update l = mid + 1
   
   

int findPeakUtil(int arr[],int low,int high, int n)
{
    int mid=(low+high)/2;
    
    if ((mid == 0 || arr[mid - 1] <= arr[mid]) &&  
        (mid == n - 1 || arr[mid + 1] <= arr[mid])) 
        return mid; 
        
     else if (mid > 0 && arr[mid - 1] > arr[mid]) 
        return findPeakUtil(arr, low, (mid - 1), n); 
        
        else
        return findPeakUtil( 
            arr, (mid + 1), high, n);
}

int peakElement(int arr[], int n)
{
    return findPeakUtil(arr, 0, n - 1, n); 
}

Complexity Analysis:

• Time Complexity: O(Logn).
  
• Space complexity: O(1).