Bitonic Peak Index

You are given an integer array nums that is bitonic: it strictly increases up to a single maximum and then strictly decreases. Formally, there is exactly one index p such that

• nums[i] < nums[i + 1] for every i < p, and
• nums[i] > nums[i + 1] for every i >= p.

Either side may be empty, so the maximum can sit at index 0 (a strictly decreasing array) or at index n - 1 (a strictly increasing array). No two adjacent values are ever equal.

Return p, the index of the maximum.

You must write an algorithm that runs in $O(\log n)$ time.

Examples

Example 1

Input: nums = [1,2,3,1]
Output: 2
Explanation: The array rises 1 < 2 < 3 and then falls 3 > 1, so the maximum 3 is at index 2.

Example 2

Input: nums = [9,7,4,1]
Output: 0
Explanation: The array only ever falls, so the increasing side is empty and the maximum is the first element.

Example 3

Input: nums = [1,4,8]
Output: 2
Explanation: The array only ever rises, so the decreasing side is empty and the maximum is the last element.