LeetCode 162. Find Peak Element

문제 링크

https://leetcode.com/problems/find-peak-element/?envType=study-plan-v2&envId=top-interview-150

문제 해석

• 0부터 시작하는 숫자 배열
• Peak element 찾아서 index 를 return
• 배열내 , Peak 다수 보유시 아무 Peak return
• 항상 Peak 는 존재
• 시간 복잡도는 O(logn) 을 준수

문제 해결

• 경계 값을 설정
  => 경계 값인 경우 와 일반적인 경우

1. index 가 0일 시 , index 1의 값보다 크면 Okay
2. index 가 끝일 시 , index n-1 값보다 크면 Okay
3. 가 아닐 시 , k-1 값과 k+1 값보다 크면 Okay

• mid 의 값이 그 전보다 클 시 , 무조건 mid 보다 왼쪽 부분이므로 left = mid +1
• else 인 경우에는 right = mid - 1

슈도 코드

if(nums[0]>nums[1])
	return 0
if(nums[last]> nums[last-1])
	return last
while left<=right:
	if ( nums[mid]>nums[mid-1] and nums[mid]>nums[mid+1])
    	return mid
    if (nums[mid]>nums[mid-1])
    	left = mid +1
    else
    	rigth = mid - 1

• 결국 , 가장 큰 값을 향해 가므로 , 답이 나온다.

결과

사담

이진 검색의 가장 기본적인 문제인거 같다.
범위를 잘 지정해서 , 풀면 매우 깔끔하고 단순하게 풀 수 있는 문제 같다.

메모본