문제
길이 n의 오름차순 정렬 배열이 1부터 n까지 회전되었다고 가정해보자. 예를 들어, 배열 nums = [0,1,2,4,5,6,7]이라면,
[4,5,6,7,0,1,2]는 4번 회전되었다.
[0,1,2,4,5,6,7]는 7번 회전되었다.
배열 [a[0], a[1], a[2], ..., a[n-1]]을 1번 회전하면 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]가 된다.
고유 요소로 구성된 정렬된 회전 배열 nums가 주어지면, 이 배열의 최소 요소를 반환하라.
O(log n) 시간 내에 알고리즘을 작성해야 한다.
풀이
가장 작은 원소를 찾고, 그 원소의 인덱스를 반환한다.
앞서 풀었던 문제와 비슷하다.
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
int mid = 0;
while (left <= right) {
mid = (left + right) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] == nums[right]) {
right--;
} else {
right = mid;
}
}
return nums[left];
}
}