Finding the maximum element in a bitonic array

Basically we need to find the point at which the elements start decreasing. It can be anywhere in the array.

The obvious linear search for maximum takes O(n) time. But we can utilize the sorted property of two parts of the arrays to solve it in O(log n).

Here is how the algorithm works.

• Go to the middle element and check if it is greater than both the left and right elements. If it is, then we found the maximum element. 
• Eg: {1, 3, 5, 4, 2}

• If the left element is greater than the middle element, we can ignore the right half and search only in left half. 
• Eg: {1, 5, 4, 3, 2}

• If the right element is greater than the middle element, we can ignore the left half and search only in right half.
• Eg: {1, 5, 7, 9, 3}

We need to handle the cases where the middle element falls on the boundaries of the array. This happens when the entire array is sorted either in ascending order or descending order. Eg: {1, 2, 3, 4, 5} or {5, 4, 3, 2, 1}

• If the right part is empty, and the middle element is greater than left element, we can eliminate the left part.
• Similarly if the left part is empty, and the middle element is greater than right element, we can eliminate the right part.

Test cases:

1. {1, 3, 5, 4, 2}
2. {1, 2, 3, 4, 5}
3. {5, 4, 3, 2, 1}
4. {1}
5. {1, 2, 2, 4, 5, 3}
6. {10, 20}

 Here is the iterative C++ implementation of the above algorithm.