A peak is a number that is strictly bigger than the numbers right next to it. Given a 0-indexed integer array nums, return the index of a peak.
Think of nums[-1] and nums[n] (just outside the array) as -∞. So the first or the last element of the array can be a peak if it is bigger than its only neighbour.
For this judge, every test array has just one peak, so only one index is correct. (In general, for an array with several peaks, the index of any one of them is fine.)
Your solution must run in O(log n) time.
Examples
Example 1:
Input: nums = [1,3,2]
Output: 1
Explanation: 3 is bigger than both of its neighbours, so the answer is index 1.
Example 2:
Input: nums = [8,6,4,2]
Output: 0
Explanation: The first number 8 is bigger than its only neighbour 6, so index 0 is the peak.
Example 3:
Input: nums = [2,5,7,9,4]
Output: 3
Explanation: The numbers go up to 9 and then fall to 4. The only peak is 9, at index 3.