C++ Program to Find the peak element of an array using Binary Search approach

Code:

#include   iostream

using namespace std;

// A function implementing Binary search approach to find a peak.
int PeakSearch(int a[], int start, int end)
{
int i, mid;
// Assigning middle of the array.
mid = (end+start+1)/2;
// If mid is at boundary index of the array sub-part, and higher than its only neighbor the mid is the peak of array. 
if((a[mid] > a[mid+1] && mid == start)||(a[mid] > a[mid-1] && mid == end))
{
return a[mid];
}
// If mid is higher than its neighbors then it is the peak element.
else if(a[mid] > a[mid-1] && a[mid] > a[mid+1])
{
return a[mid];
}
// If right neighbor is higher then right subpart must have a peak.
else if(a[mid] <= a[mid+1])
{
return PeakSearch(a, mid+1, end);
}
// If left neighbor is higher then left subpart must have a peak.
else if(a[mid] <= a[mid-1])
{
return PeakSearch(a, start,mid-1);
}
}

int main()
{
int n, i, peak;
cout<<"\nEnter the number of data element: ";
cin>>n;

int arr[n];
// Take data input.
for(i = 0; i < n; i++)
{
cout<<"Enter element "<
cin>>arr[i];
}

// Get the peak of the array.
peak = PeakSearch(arr, 0, n-1);

// Print the result.
cout<<"\nThe peak element of the given array is: "<

    return 0;
}


Output:

Enter the number of data element: 20
Enter element 1: 3
Enter element 2: 9
Enter element 3: 16
Enter element 4: 45
Enter element 5: 91
Enter element 6: 156
Enter element 7: 984
Enter element 8: 784
Enter element 9: 653
Enter element 10: 641
Enter element 11: 599
Enter element 12: 481
Enter element 13: 411
Enter element 14: 321
Enter element 15: 222
Enter element 16: 198
Enter element 17: 47
Enter element 18: 43
Enter element 19: 22
Enter element 20: 1

The peak element of the given array is: 984



More C++ Programs: