You are given a sequence nums in which no two neighbouring values are equal. Pretend there is an extra value of negative infinity just before index 0 and just after the last index. An index i is a peak if nums[i] is strictly greater than both of its neighbours (using those imaginary infinities at the ends).
Write find_peak(nums) that returns the index of any peak. At least one always exists.
You must use O(log n) reads. The tests pass in a read-only sequence that supports only len(nums) and nums[i]; it can be a billion elements long and counts your reads.
find_peak([4, 7, 3]) # 1
find_peak([1, 6, 2, 8, 9, 0]) # 1 or 4
find_peak([5]) # 0
find_peak([3, 2, 1]) # 0
Constraints: 1 <= len(nums), nums[i] != nums[i + 1].
Show hint
If nums[mid] < nums[mid + 1], walking right from mid must eventually hit a peak (values can't climb forever before the imaginary cliff at the end). What does that let you discard?