Problem statement

https://leetcode.com/problems/find-peak-element/

Solution

There is a huge hint given in the problem description: we need to find solution with complexity O(log n) and we immedietly must think about binary search. Let us consider the case [-inf, 1, 2, 1, 3, 5, 6, 4, inf]. We need to find place k, such that nums[k] < nums[k+1] and nums[k+1] > nums[k+2]. Let us compare all pairs of adjacent elements and ask question: if the first one is smaller then the second, for our array we have [True, True, False, True, True, True, False, False]. Then what we need to find in this array is any two adjacent places where we have pair True, False. Note, that first element is always True and last is always False, so we have True, .............., False.

Now, let us choose element in the middle, and we can have two options: 1) It is True, so we have True, ......, True, ......., False and in this case for the second half we have property that it starts with True and ends with False. 2) It is False, so we have True, ......, False, ......., False and in this case for the first half we have property that it starts with True and ends with False.

So, in any case we save the property that it starts with True and ends with False. Each time we decrease length of interal twice, so:

Complexity

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

Code

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

        return end