Problem statement

https://leetcode.com/problems/peak-index-in-a-mountain-array/

Solution 1

We need to find place, for which difference between two adjacent element changes its sign, so we can just do binary search.

Complexity

Time complexity is O(log n), space is O(1).

Code

class Solution:
    def peakIndexInMountainArray(self, arr):
        beg, end = 0, len(arr) - 1
        while beg < end:
            mid = (beg + end) // 2
            if arr[mid] < arr[mid + 1]:
                beg = mid + 1
            else:
                end = mid
        return beg

Solution 2

There is also ternary search for the cases, when function is not discrete.

Complexity

Time complexity is O(log n), in fact it is O(log3 n).

Code

class Solution:
    def peakIndexInMountainArray(self, arr):
        beg, end = 0, len(arr) - 1
        while end - beg > 2:
            mid1, mid2 = (2*beg + end)//3, (beg + 2*end)//3
            if arr[mid1] > arr[mid2]:
                end = mid2
            else:
                beg = mid1
                
        return beg + 1