[리트코드] 162. Find Peak Element

https://leetcode.com/problems/find-peak-element/

Find Peak Element - LeetCode

---

그냥 최댓값 원소의 인덱스 반환해주면 되는 문제인 줄 알았는데 아니었다..!

좌우 원소보다 큰 원소를 발견하면 그냥 바로 return 해주면 되는 문제였다

그러나 이걸 for문으로 반복해서 풀면 O(logN)안으로 해결이 안되니까 이진탐색을 이용해서 구현한 것이었따!!

 

문제는 되게 쉬운데 같은 스터디하시는 분 말씀으로는 코드가 진짜 짧게 구현이 가능해서 medium인 것 같다고 하셨다

근데 난 아무리 생각해도 한 줄만에 끝나는 걸 모르겠어서 solution을 봤는데 이진탐색으로 구현했더라구

이진탐색... 좋지....

성능은 되게 좋은 것 같더라구

 

처음엔 최댓값 반환해야되는 줄 알고 '정렬도 안하고 이진탐색 하면 무슨 의미지..?'했는데

그냥 [peak element]가 존재하면 반환하면 되는거였다!!

 

오.. 이렇게 보니까 medium같긴 하다..

 

 

 

자바 코드)

class Solution {
    public int findPeakElement(int[] nums) {
        if(nums.length == 1) return 0;
        
        int start = 0;
        int end = nums.length-1;
        
        while(start<end) {
            int mid = (start + end) /2;
            if(nums[mid] > nums[mid+1]) {
                end = mid;
            } else {
                start = mid+1;
            }
        }
        return start;
    }
}