Find the maximum element in an array which is first increasing and then decreasing in C++\\n

Suppose we have one array, which is initially increasing then decreasing. We have to find the max value in the array. So if the array elements are like A = [8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1], then output will be 500.

We can use the binary search to solve this. There are three conditions −

• When mid is greater than both of its adjacent elements, then mid is maximum
• If mid is greater than the next element, but smaller than previous element, then max lies on the left side of mid.
• If mid element is smaller than the next element, but greater than previous element, then max lies on the right side of mid.

Example

 Live Demo

#include<iostream> using namespace std; int getMaxElement(int array[], int left, int right) {    if (left == right)       return array[left];    if ((right == left + 1) && array[left] >= array[right])       return array[left];    if ((right == left + 1) && array[left] < array[right])       return array[right];    int mid = (left + right)/2;    if ( array[mid] > array[mid + 1] && array[mid] > array[mid - 1])       return array[mid];    if (array[mid] > array[mid + 1] && array[mid] < array[mid - 1])       return getMaxElement(array, left, mid-1);    else       return getMaxElement(array, mid + 1, right); } int main() {    int array[] = {8, 10, 20, 80, 100, 250, 450, 100, 3, 2, 1};    int n = sizeof(array)/sizeof(array[0]);    cout << "The maximum element is: " << getMaxElement(array, 0, n-1); }

Output

The maximum element is: 450