programming-practice/binary_search/medium/peak_element.py at master · sindhura-pv/programming-practice · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:

        if not nums:
            return -1

        if len(nums) == 1:
            return 0

        def ispeak(i):

            if nums[i]>nums[i-1] and nums[i]>nums[i+1]:
                return True
            return False

        nums = [float('-inf')] + nums + [float('-inf')]
        n = len(nums)

        left = 1
        right = n-1

        while left+1 < right:

            mid = (left+right)//2

            if ispeak(mid):
                return mid-1

            if nums[mid+1] > nums[mid]:
                left = mid

            else:
                right = mid

        if ispeak(left):
            return left-1

        if ispeak(right):
            return right -1


        return -1