Find Peak Element

문제

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

Given a 0-indexed 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] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

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

풀이

• Olog(n)으로 풀이하라고 주어짐!
• peak element: 양 옆의 원소보다 더 큰 수
• 배열의 양 끝은 무한이므로 배열 안에서 peak element는 반드시 존재함
  • 배열의 양 끝이 다른것보다 작을 때, peak element가 됨
• 이진탐색으로 배열의 mid 값을 확인
  • nums[mid] < nums[mid + 1]: start = mid + 1로 갱신함
  • nums[mid] >= nums[mid + 1]: end = mid

수도 코드

시작 = 0
끝 = nums의 길이 - 1

while 시작 < 끝:
	중간값 = (시작 + 끝) / 2
    
    if nums[중간값] < nums[중간값 + 1]:
    	시작을 중간값 + 1로 갱신
    else:
    	끝을 중간값으로 갱신
        
return 시작

Solution(Runtime: 54ms)

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        start, end = 0, len(nums) - 1

        while start < end:
            mid = (start + end) // 2

            if  nums[mid] < nums[mid + 1]:
                start = mid + 1
            else:
                end = mid
        
        return start

순차적으로 탐색해서 O(n)으로 찾아낼 수 있지만 문제에서 O(logn)의 풀이를 요구하고 있다. 따라서 범위를 나타내는 start, end 인덱스 값을 이용해 이진 탐색으로 범위를 반복할때마다 반으로 줄여 O(logn)의 풀이가 가능하다.