A mountain is a sequence of at least 3 numbers that strictly rises to a single highest value and then strictly falls. Write peak_index(arr) that returns the index of that highest value.
Your function must use O(log n) reads. The tests pass in a read-only sequence object that supports only len(arr) and arr[i]; it can be a billion elements long and counts how many times you index it. A linear scan is too slow, and slicing or copying it is not supported.
peak_index([2, 5, 9, 4]) # 2
peak_index([1, 3, 2]) # 1
peak_index([0, 10, 8, 6, 4, 2]) # 1
Constraints: 3 <= len(arr), arr is guaranteed to be a mountain.
Show hint
Look at arr[mid] and arr[mid + 1]: whether you are still going uphill tells you which side of mid the peak is on. (A ternary search on this unimodal sequence also works, with a few more reads.)