[LEETCODE] 162: Find Peak Element(Python)

Find Peak Element - LeetCode

문제 설명

주어진 배열에서 극댓값을 찾는 문제이다.

나의 풀이

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l=len(nums)
        nums=[(-1)*sys.maxsize]+nums+[(-1)*sys.maxsize]
        s=0
        e=len(nums)-1
        while s<e or s<l-1 or e>0:
            k=(s+e)//2
            if nums[k-1]>nums[k]:
                e=k-1
            elif nums[k+1]>nums[k]:
                s=k+1
            elif nums[k-1]<nums[k] and nums[k+1]<nums[k]:
                return k-1

이분 탐색을 통해 단순 순회보다 빠르게 문제를 해결할 수 있다. 해당 문제 풀이는 여기서 자세하게 설명해 두었다.

시간복잡도

이분 탐색을 사용하여 O(logn)의 시간복잡도를 가진다.