회전된 배열에서 최소값 찾기 (java)
역시 정렬된 상태에서 회전된 배열입니다.
[1,2,3,4,5]
[2,3,4,5,1]
[3,4,5,1,2]
[4,5,1,2,3]
[5,1,2,3,4]
위와 같은 크기 5짜리 배열의 구성이 있다고 가정하고 시작합니다.
1. midIndex 기준으로 최소값 판별
mid = (start + end) / 2;
역시 midIndex를 계산후에... 최소값의 기준이 되는 조건에 대해서 생각해봅니다.
- 내가 앞 인덱스보다 작다. -> 내 인덱스는 최소값이다.
- 내가 뒤 인덱스보다 크다. -> 뒤 인덱스가 최소값이다.
mid Index를 기준으로 앞뒤 체크를 한뒤... 이진탐색을 이어가면 됩니다.
문제는 탐색 구간을 나누는 일이겠네요.
2. 이진 탐색 구간 나누기
먼저 회전된 배열에서 값 찾기 처럼 구간을 나눠보겠습니다.
- 'start~mid' 구간이 정렬되어 있는 경우
하지만 문제가 있습니다. 위의 경우에
[1,2,3,4,5]
[2,3,4,5,1]
[3,4,5,1,2]
의 배열 조합이 해당되는데... 최소값인 1이 왼쪽 오른쪽에 사이좋게 나누어져 있습니다. 'start~end' 구간이 정렬된 경우로는 탐색 구간 나누기가 불가능하겠네요.
그렇다면 반대의 경우로...
- 'mid~end' 구간이 정렬되어 있는 경우
[1,2,3,4,5]
[4,5,1,2,3]
[5,1,2,3,4]
최소값인 1이 왼쪽 혹은 mid 에 분포하고있네요. [4,5,1,2,3]인 경우에는 이미 위에서 판별되었을 테니.. 해당 조건으로 이진탐색을 이어가면 될거같습니다.
정리하자면...
'mid~end' 구간이 정렬되어 있는 경우에는 start, (mid-1) 구간 이진 탐색, 아닌 경우에는 (mid+1), end 구간 이진 탐색으로 진행하면 되겠네요.
{
int[] arr = new int[]{1, 2, 3, 4, 5};
int idx = findMinIndex(arr, 0, arr.length - 1);
assert (0 == idx);
arr = new int[]{2, 3, 4, 5, 1};
idx = findMinIndex(arr, 0, arr.length - 1);
assert (4 == idx);
arr = new int[]{3, 4, 5, 1, 2};
idx = findMinIndex(arr, 0, arr.length - 1);
assert (3 == idx);
arr = new int[]{4, 5, 1, 2, 3};
idx = findMinIndex(arr, 0, arr.length - 1);
assert (2 == idx);
arr = new int[]{5, 1, 2, 3, 4};
idx = findMinIndex(arr, 0, arr.length - 1);
assert (1 == idx);
} public static int findMinIndex(int[] arr, int start, int end) {
if (end <= start) {
return start;
}
int mid = (start + end) / 2;
if (start <= (mid - 1) && arr[mid - 1] > arr[mid]) {
return mid;
}
if ((mid + 1) <= end && arr[mid] > arr[mid + 1]) {
return mid + 1;
}
if (arr[mid] < arr[end]) {
return findMinIndex(arr, start, mid - 1);
}
return findMinIndex(arr, mid + 1, end);
}출처 - POCU 아카데미 COMP3500 강의내용 응용
