162. Find Peak Element

---

문제 분석

정수 배열이 하나 주어진다.

Peak 이란 아래의 조건을 충족해야 한다.
1. nums[n] > nums[n-1]
2. nums[n] < nums[n+1]

해당 조건이 충족하는 숫자의 인덱스 n 을 리턴하는 문제.

---

풀이 과정

정답이 되기 위한 조건은 아래와 같다.
nums[n] 은 nums[n - 1] 과 nums[n + 1] 보다 커야한다.
만약에 n 이 배열의 마지막 인덱스라면 n 은 [n - 1] 보다 크면 성립.
만약에 n 이 배열의 첫번째 인덱스라면 n 은 [n + 1] 보다 크면 성립.

이분 탐색으로 접근한 이유는
배열을 절반씩 잘라가며 특정 조건식으로 찾아가기 때문에 시간 복잡도 성능이 꽤나 좋다.
(조건에 해당하지 않는 나머지 배열(n/2)은 탐색하지 않고 버리기 때문.)

🤔 이 문제를 풀기위해 어떤 조건이 성립하는지 예제를 통해 설명한다.

ex) nums = [1, 2, 1, 3, 5, 6, 4]

위의 예제 배열에서
시작 인덱스는 startIndex = 0
마지막 인덱스는 endIndex = 6
중간 인덱스는 midIndex = 3

• 중간 인덱스를 구하는 식은 (startIndex + endIndex) / 2

중간값 nums[midIndex] 과 오른쪽 값 nums[midIndex + 1] 를 비교한다.

만약에 nums[midIndex] 보다 nums[midIndex + 1] 이 크다면
시작 인덱스를 startIndex = midIndex + 1 로 바꿔준다.
아니라면 endIndex = midIndex 로 바꿔준다.

startIndex 가 endIndex 보다 작다면 계속 반복문을 돌며 index 들을 업데이트한다.

🤔 위의 조건이 성립하는 이유는....

여러개의 정답이 있을 수도 있지만 정답인 인덱스 아무거나 하나만 리턴하면 되기 때문이다.
midIndex 보다 midIndex + 1 가 작다면 midIndex - 1 만 비교해보면 되기 때문에 해당 값이 정답일 확률이 올라간다.

반대로
midIndex 보다 midIndex + 1 가 크다면 midIndex + 1 을 기준으로 이미 왼쪽 인덱스인 midIndex 가 작다는 것이고 midIndex + 2 만 비교해보면 되기 때문에 해당 값이 정답일 확률이 올라간다.

이러한 로직을 바탕으로 이분 탐색을 하면 주어진 시간 복잡도내에 해결할 수 있다.

---

나의 생각

이분 탐색을 활용한 탐색 방법은 간단하면서도 무궁무진한 것 같다.
문제 출제가 어떤식으로 되고 내가 어떻게 이해하냐에 따라 쉽게 풀 수도
어렵게 풀 수도 있는 것 같다.

---

코드

    public int findPeakElement(int[] nums) {
        int startIndex = 0;
        int endIndex = nums.length - 1;

        while (startIndex < endIndex) {
            int midIndex = (startIndex + endIndex) / 2;
            int midRightIndex = midIndex + 1;
           
            if (nums[midIndex] > nums[midRightIndex]) {
                endIndex = midIndex;
            } else {
                startIndex = midRightIndex;
            }
        }

        return startIndex;
    }