[LeetCode/Java] 162. Find Peak Element

0. 문제

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

1. 문제 설명

• 정수 배열이 주어질 때, 최대값의 인덱스를 반환하시오.

2. 문제 풀이

2.1. 접근법 : 탐색

• for문을 돌면서 최대값을 갱신한다.
• 코드

class Solution {
    public int findPeakElement(int[] nums) {
        int ans = 0;
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
                ans = i;
            }
        }
        return ans;
    }
}

4. 결과

5. 개선점

5.1. 시간 복잡도 개선 : 이분 탐색 적용

• O(logN)의 시간 복잡도로 풀어야 된다는 조건이 있어 이분 탐색을 적용한다.
• 중간 위치의 요소와 그 다음 위치의 요소를 비교한다.
• 만약 중간 위치의 요소가 다음 요소보다 작으면 최대값은 오른쪽에 있을 것이라고 가정하고 탐색 범위를 오른쪽으로 옮긴다.

class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

• 결과