Find maximum element in Bitonic Array

Problem statement:

Given an bitonic array, find the max element in that.

Example:

Array {1, 2, 3, 4, 5, 4, 3, 2, 1};

Output = 5

A bitonic array is an ascending sorted array where, after a particular element, the array starts descending.

In our example above, the array is ascending till element 5 and starts descending after that.

Solution:

We can solve this with help of binary search.

We need to perform below tasks:

1. If the mid element is greater than left and right element, then it is the maximum.

2. If mid element is greater than its right element and smaller than the left element, then maximum is on left side of mid. Example array: {2, 40, 9, 8, 6, 5}

3. If mid element is greater than its left element and smaller than the right element, then maximum is on right side of mid. Example array: {2, 6, 9, 8, 6, 5}

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 arr[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, 5, 4, 3, 2, 1}; 
    int len = sizeof(arr) / sizeof(arr[0]); 
    int result = binary_search(arr, len);

    cout<<"The max element of the bitonic array is  " <<result<<endl;

    return 0; 
} 

Output:

The max element of the bitonic array is 5