852. Peak Index in a Mountain Array

You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease.

Return the index of the peak element.

Your task is to solve it in O(log(n)) time complexity.
 

Example 1:

Input: arr = [0,1,0]
Output: 1

Example 2:

Input: arr = [0,2,1,0]
Output: 1

Example 3:

Input: arr = [0,10,5,2]
Output: 1

Constraints:

• $3<=arr.length<=10^5$
• $0<=arr[i]<=10^6$
• arr is guaranteed to be a mountain array.

From: LeetCode
Link: 852. Peak Index in a Mountain Array

Solution:

Ideas:

• Binary search on the “slope”: if arr[mid] < arr[mid+1], go right; else go left.

• Runs in O(log n) time and O(1) space.

Code:

int peakIndexInMountainArray(int* arr, int arrSize) {
    // Peak can't be at the ends in a valid mountain array
    int lo = 1, hi = arrSize - 2;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
            return mid; // found the peak
        } else if (arr[mid] < arr[mid + 1]) {
            // we're on the increasing slope; move right
            lo = mid + 1;
        } else {
            // we're on the decreasing slope; move left
            hi = mid - 1;
        }
    }
    // Given constraints guarantee a peak exists; return -1 for safety.
    return -1;
}