[LeetCode] 162. Find Peak Element - Java[자바]

링크

문제

Peak Element는 가장 큰 요소입니다.

정수 배열 nums가 주어졌을 때, Peak Element를 구하고 그 인덱스를 반환합니다. 배열에 여러 개의 피크가 포함되어 있으면 그 중 하나의 피크에 대한 인덱스를 반환합니다.

nums[-1] = nums[n] = -∞라고 간주할 수 있습니다. 즉, 한 요소는 항상 배열 외부에 있는 이웃 요소보다 엄격하게 큰 것으로 간주됩니다.

O(log n) 시간 내에 실행되는 알고리즘을 작성해야 합니다.

풀이

투포인터 이분탐색을 떠올렸습니다.

peek element의 특성상, 꼭 배열이 정렬되어있지 않아도, mid와 mid +1 인덱스의 값을 비교해서 점차 큰 peek가 있는 곳으로 탐색해 가면 결국 peek로 도달할 수 있는 것입니다.

예시 2번의 nums가 [1,2,1,3,5,6,4] 일 때를 예시로 들어보겠습니다.

1. left = 0, right = 6, mid는 아직 설정되지 않았습니다.
2. while 문에 진입하고 mid를 계산합니다. (left + (right - left) / 2 = 0 + (6 - 0) / 2 = 3). 따라서 mid는 3이며, nums[mid]는 3입니다.
3. numsmid는 numsmid + 1보다 작기 때문에 left를 mid + 1로 업데이트합니다. (left는 이제 4입니다)
4. 다시 mid를 계산합니다. (left + (right - left) / 2 = 4 + (6 - 4) / 2 = 5). nums[mid] 는 이제 6입니다.
5. numsmid는 numsmid + 1보다 큽니다. 따라서 right를 mid로 업데이트합니다. (right는 이제 5입니다)
6. 다시 mid를 계산합니다. (left + (right - left) / 2 = 4 + (5 - 4) / 2 = 4). nums[mid] 는 이제 5입니다.
7. numsmid는 numsmid + 1 보다 작으므로 left를 mid + 1 로 업데이트 하여 left = 5 로 합니다.
8. 이제 left와 right가 같으므로 반복문이 종료되고 left (또는 right, 값은 같습니다)가 반환됩니다.

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

정직한 이분 탐색 코드이지만, mid의 인덱스와 mid +1 인덱스의 값을 비교하는 점이 좀 다르다.