[리트코드] 162. Find Peak Element - python

162. Find Peak Element

문제

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

제한사항

• 1 <= nums.length <= 1000
• -231 <= nums[i] <= 231 - 1
• nums[i] != nums[i + 1] for all valid i.

풀이

최대 O(logN)으로 풀어야하므로 이진탐색으로 해결할 수 있다.

절반을 나눠 시작해서 피크인지 확인하고 다음 값이 더 크면 오른쪽 더 작으면 왼쪽으로 이동해서 다시 탐색한다.

왼쪽으로 이동할 때에는 mid 값이 피크가 될 수도 있으므로 mid로 옮겨준다.

피크인 지점에서 left와 right가 만나며 종료되게 된다.

둘 중에 아무거나 리턴해도 상관 없다.

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        if len(nums) <= 1:
            return 0
        
        while left < right:
            mid = (left + right) // 2
                
            if nums[mid] < nums[mid + 1]:
                left = mid + 1
            else:
                right = mid
                
        
        return left