PEAK ELEMENT-BINARY SEARCH

 PROBLEM STATEMENT:

We are given an array. We have to determine the index of peak element. Peak element is the element that is greater than both of it's neighbors. If i is the index of peak element, then array[i] will be greater than both array[i-1] and array[i+1].

QUICK POINTS:

1. Number of peak element can be more than one.

2. If middle element comes out to be greater than both of it's neighbors, then this will become the peak element.

3. If the middle element is not the peak element, then we have two options, either we will go right side to find the element or to the left side.

4. If the right neighbor of the middle element is greater than the middle element, then we will go towards right to search, else we will go towards left.

CODE:

#include <bits/stdc++.h>

using namespace std;

int binsearch(int l,int r,int a[],int n)

{

    if(r>=l){

    int middle=l+(r-l)/2;

    if(middle>0 && middle<n-1 && a[middle]>a[middle-1] && a[middle]>a[middle+1])

        return a[middle];

    else if(middle==0 && a[middle]>a[middle+1])

        return a[middle];

    else if(middle==n-1 && a[middle]>a[middle-1])

        return a[middle];

    else if(a[middle-1]>a[middle])

        return binsearch(0,middle-1,a,n);

    else if(a[middle]<a[middle+1])

        return binsearch(middle+1,r,a,n);

    }

    return -1;      //if the element doesn't exist

}

int main()

{

    int n;

    cin>>n;

    int a[n];

    for(int i=0;i<n;i++)

        cin>>a[i];

    int ans=binsearch(0,n-1,a,n);

    cout<<ans;

    return 0;

}

INPUT:

7

10    20    15    10    20    50    60

OUTPUT

20