Problem¶

An array arr a mountain if the following properties hold:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given a mountain array arr, return the index i such that arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

You must solve it in O(log(arr.length)) time complexity.

Example 1:

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

Constraints:

• 3 <= arr.length <= 105
• 0 <= arr[i] <= 106
• arr is guaranteed to be a mountain array.

Solve¶

Linear¶

Create a pointer left at the start and a pointer right at the end of the array. Loop using there:

• If arr[left] <= arr[right]: increase Left
• else: arr[left] > arr[right]: increase Right
• Stop when left == right
  Because we always can found arr[left] < arr[i] > arr[right], so the function stop at left == right == i

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        l, r = 0, len(arr) - 1
        while l != r:
            if arr[l] <= arr[r]:
                l += 1
            else:
                r -= 1
        return l

Using Binary Search to Find the Maximum Value in a Discrete Parabolic-Like Array (Gave up)¶

This could possibly use in all discrete Parabolic search

Intuition¶

In a mountain array with peak index i, any element at index with index less than i would obey arr[index] < arr[index + 1]. Furthermore, any index greater than or equal to i would follow the rule arr[index] > arr[index + 1] (and not obey arr[index] < arr[index + 1]).

A scenario like this where our task is to search for an element i from a given range (l, r) where all values smaller than i satisfy a certain condition and all values greater than or equal to i do not satisfy it (or vice-versa) can be solved optimally with a binary search algorithm. In binary search, we repeatedly divide the solution space where the answer could be in half until the range contains just one element.

Following the above discussion, we use binary search to solve this problem. We create an integer l and initialize it to the starting index 0. We also create another integer variable r and set it to the last index of arr, i.e., arr.length - 1.

We get the middle of the range mid = (l + r) / 2 and compare arr[mid] with the next element. If arr[mid] < arr[mid + 1], we move to the upper half of the range by setting l = mid + 1 as our peak index is definitely greater than mid. Otherwise, if arr[mid] > arr[mid + 1], we move to the lower half of the range by setting r = mid as the peak index is either mid or some index smaller than mid.

The answer would be within the range (l, r) at any point. All the indices smaller than l are indices smaller than the peak index and all indices greater than r are indices greater than the peak index. We continue the search as long as l < r.

When l == r, l (or r) denotes the required peak index.

Here is a visual representation of an example to illustrate how it works:

Algorithm¶

1. Create two integer variables l and r to store the solution space of the problem. We initialize l with 0 and r to arr.length - 1.
2. While l < r:
   • Get the index of the middle element using mid = (l + r) / 2.
   • If arr[mid] < arr[mid + 1], it indicates peak index is greather than mid. As a result, we move to upper half of the range by setting left = mid + 1.
   • Else, if arr[mid] >= arr[mid + 1], it indicates that the peak index is either mid or some index smaller than mid. As a result, we move to the lower half of the range by setting r = mid.
3. Return l (or r as both are equal now).

Implementation¶

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        l = 0
        r = len(arr)
        while l < r:
            mid = (l + r) // 2
            if arr[mid] < arr[mid + 1]:
                l = mid + 1
            else:
                r = mid
        return l