Peak Element

Problem Statement:

You are given an unsorted array and you need to send the index of peak element.

Understanding what is Peak element?

1. An element who is greater than both of its neighbor.
Example array = {1, 2, 5, 4, 3}. Here peak element is 5 and index is 2.

2. An element, if it is beginning of the array, and is greater than the element to its right then it is a peak element.
Example array = {6, 2, 3, 4, 5}. Here peak element is 6 and index is 0. This is because, 6 will not have previous index as it is -1.

3. An element, if it is end of the array, and is greater than the element to its left then it is a peak element.
Example array = {1, 2, 3, 4, 5, 6}. Here peak element is 6 and index is 5. This is because, 6 will not have next index as it is out of bounds.

Solution:

We can solve this problem with help of binary search.

Now we need to find out a logic to find if the mid element is a peak element or not.

1. Here we need to check if the mid element is greater than mid+1 and mid-1.

For that we can write the logic as if(array[mid – 1] <= array[mid]) && array[mid] >= array[mid + 1]).

2. Then we need to check if the mid is 0 or mid is n-1 if mid is 0, then it should be greater than mid+1
For that we can write

if(mid == 0 && array[mid] >= array[mid + 1])

3. Similarly if mid is n-1, then it should be greater than mid-1

For that we can write

if(mid == n-1 && array[mid-1] <= array[mid])

We can combine above 3 statements into a single statement as below:

if ((mid == 0 || array[mid – 1] <= array[mid]) && (mid == n – 1 || array[mid] >= array[mid + 1])) {

4. Now we need to check if we need to go left or right?

We just need to check, in which side the element is greater than the mid element.
If the element towards right of mid element is greater, then move towards right.
else
If the element towards left of mid element is greater, then move towards left.

For that we can write the logic as below:

if (mid > 0 && arr[mid – 1] > arr[mid])
{
end = mid – 1;
} else {
start = mid + 1;
}

Solution in C++

#include <iostream>
using namespace std;

int binary_search(int arr[], int len) 
{ 
    int start = 0;
    int end = len - 1;
  
          while (start <= end) 
          {
              int mid = (start + end) / 2;
  
              if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == len - 1 || arr[mid] >= arr[mid + 1])) 
              {
                  return mid;  
              } else if (mid > 0 && arr[mid - 1] > arr[mid]) 
              {
                  end = mid - 1;
              } else {
                  start = mid + 1;
              }
        } 
    return -1;
}

int main(void) 
{ 
    int arr[] = {1, 2, 3, 4, 8, 6, 7}; 
    int len = sizeof(arr) / sizeof(arr[0]); 
    int result = binary_search(arr, len);

    cout<<" The index of peak element is found at " <<result<<endl;

    return 0; 
} 

Output:

The index of peak element is found at 4