문제
'피크'란 주변 요소보다 큰 값을 가진 요소를 의미합니다. 배열 내에 여러 개의 피크가 있을 수 있으며, 이 중 하나를 찾으세요.
문제 접근 방식
배열을 탐색하며, 한 요소에 대해 왼쪽 요소와 오른쪽 요소를 비교해서 큰 값을 찾아야 하는 문제이기 때문에, 선형 탐색보다는 이진 탐색을 통해 문제를 해결하는것이 시간복잡도도 작고, 쉽게 풀수 있을것같아 이진 탐색을 활용했습니다.
중간값(mid)과 그 주변 값들을 비교하여 어느 쪽으로 탐색할 것인지 결정합니다. 만약 mid 값이 양 옆 값보다 크다면, 우리가 찾고 있는 '피크'임으로 해당 인덱스를 반환합니다. 그렇지 않으면 mid값이 오른쪽 값보다 작으면 왼쪽 범위(left)를 조정하고, 반대로 왼쪽 값보다 작으면 오른쪽 범위(right)를 조정하여 탐색 범위를 줄입니다.
CODE
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
if (nums.length == 1)
return 0;
if (nums[right] > nums[right - 1])
return right;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[0] > nums[1])
return 0;
if(nums[mid]>nums[mid+1] && nums[mid]>nums[mid-1])
return mid;
if(nums[mid]<nums[mid+1])
left = mid + 1;
else
right = mid;
}
return left;
}
}
