정렬된 배열이 어느 한 지점(피벗)을 기준으로 회전되어 있다고 가정해 보겠습니다. 피벗의 위치는 미리 알 수 없으며, 우리의 목표는 이 배열에서 최솟값을 찾는 것입니다. 예를 들어 배열이 [4,5,5,5,6,8,2,3,4]와 같다면 최솟값은 2입니다.
이 문제의 핵심은 배열에 중복 요소가 포함될 수 있다는 점입니다. 중복이 없는 일반적인 회전 정렬 배열이라면 단순한 이진 탐색으로 O(log n)에 해결할 수 있지만, 중복이 존재하면 arr[low] == arr[mid]와 같은 모호한 상황이 발생해 어느 쪽 구간이 정렬되어 있는지 판별할 수 없게 됩니다. 이럴 때는 탐색 범위를 한 칸씩 줄여가며 확인해야 합니다.
해결 접근 방법
- search()라는 재귀 메서드를 정의합니다. 이 메서드는 배열 arr과 탐색 범위의 양 끝 인덱스인 low, high를 매개변수로 받습니다.
- low == high이면 탐색 범위에 원소가 하나뿐이라는 의미이므로 arr[low]를 반환합니다.
- mid := low + (high - low) / 2로 중간 인덱스를 계산합니다.
- ans를 무한대(INF)로 초기화합니다.
- arr[low] < arr[mid]인 경우: 왼쪽 구간이 정렬되어 있으므로 ans := min(arr[low], search(arr, mid, high))
- 그렇지 않고 arr[high] > arr[mid]인 경우: 오른쪽 구간이 정렬되어 있으므로 ans := min(arr[mid], search(arr, low, mid))
- 그렇지 않고 arr[low] == arr[mid]인 경우: 어느 쪽이 정렬된 상태인지 판별할 수 없으므로 왼쪽 경계를 하나 줄여 ans := min(arr[low], search(arr, low + 1, high))
- 그렇지 않고 arr[high] == arr[mid]인 경우: 마찬가지로 판별이 불가능하므로 오른쪽 경계를 하나 줄여 ans := min(arr[high], search(arr, low, high - 1))
- 마지막으로 ans를 반환합니다.
main 함수에서는 search(nums, 0, nums.size() - 1)를 호출하여 전체 배열에 대한 최솟값을 구합니다.
예제 코드
다음은 위 알고리즘을 C++로 구현한 예제입니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int search(vector <int>& arr, int low, int high){
if(low == high){
return arr[low];
}
int mid = low + (high - low) / 2;
int ans = INT_MAX;
if(arr[low] < arr[mid]){
ans = min(arr[low], search(arr, mid, high));
}
else if (arr[high] > arr[mid]){
ans = min(arr[mid], search(arr, low, mid));
}
else if(arr[low] == arr[mid]){
ans = min(arr[low], search(arr, low + 1, high));
}
else if(arr[high] == arr[mid]){
ans = min(arr[high], search(arr, low, high - 1));
}
return ans;
}
int findMin(vector<int>& nums) {
return search(nums, 0, nums.size() - 1);
}
};
main(){
Solution ob;
vector<int> v = {4,5,5,5,6,8,2,3,4};
cout <<(ob.findMin(v));
}입력
[4,5,5,5,6,8,2,3,4]
출력
2
복잡도 분석
평균적인 경우 시간 복잡도는 이진 탐색에 기반하므로 O(log n)입니다. 하지만 모든 원소가 같은 값인 최악의 경우에는 매번 탐색 범위가 한 칸씩만 줄어들어 O(n)까지 증가할 수 있습니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 평균적으로 O(log n)입니다.