472. Find Maximum of Bitonic Sequence

Given a bitonic (mountain) array arr that first strictly increases then strictly decreases, return the maximum element. Solve in O(log n).

Input: A bitonic integer array arr.

Output: The maximum element (peak value).

Examples

Input: [1,3,5,4,2]
Output: 5
Explanation: Peak value is 5 at index 2.

Input: [0,1,2,1,0]
Output: 2
Explanation: Peak is 2 at index 2.

Input: [1,2,3,4,5,4]
Output: 5
Explanation: Peak is 5 at index 4.

Constraints

• 3 <= arr.length <= 10^5
• 0 <= arr[i] <= 10^6
• Strictly increases then strictly decreases

Asked by