How To Find Maximum Element In a Bitonic Array?

 PROBLEM STATEMENT:

We are given a bitonic array. We have to find the maximum element. Bitonic array is an array which elements first increases monotonically from left to right, then after some point, it starts decreasing monotonically.

ALGORITHM

The question is similar to peak element, the only difference is that in peak element problem, there are multiple answers possible, but in this problem, there is only one answer is possible. Check algorithm here:

https://www.cuplex2b.com/2021/01/peak-element-binary-search.html

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:

6

10    20    30    15    10    5

OUTPUT:

30