문제
정렬된 배열이 어느 피벗을 기준으로 회전되어 있다. 예를 들어, [0,1,2,4,5,6,7]이 [4,5,6,7,0,1,2]로 회전되었다고 가정해봅시다. 이런 배열에서 최소값을 찾으시오
접근방식
배열에서 최솟값을 찾으면 되기 때문에, 선형 탐색 대신 시간복잡도가 작은 이진 탐색을 활용하여 문제를 해결했습니다.
먼저 left와 right 포인터를 초기화합니다.
while 루프를 돌면서 중간값(mid)과 오른쪽 값(nums[right])을 비교합니다.
만약 중간값이 오른쪽 값보다 작다면 최솟값은 왼쪽에 위치하므로 오른쪽 범위(right)를 조정합니다.
만약 중간값이 오른쪽 값보다 크다면 최솟값은 오른쪽에 위치하므로 왼쪽 범위(left)를 조정합니다.
만약 중간값과 오른쪽 값이 같다면 현재의 right 포인터가 가리키는 값을 제외하고 계속 검사합니다.
모든 가능한 범위에서 검사한 후 마지막 남은 요소가 최소값입니다.
CODE
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if(nums[mid] < nums[right])
right = mid;
else if(nums[mid] > nums[right])
left = mid + 1;
else
right--;
}
return nums[left];
}
}
