문제 개요
오름차순으로 정렬된 배열이 있다고 가정해 봅시다. 이 배열은 우리가 미리 알 수 없는 어떤 피벗(pivot)을 기준으로 회전되어 있습니다. 예를 들어 [0,0,1,2,2,5,6]과 같은 배열은 회전 과정에서 [2,5,6,0,0,1,2]로 바뀔 수 있습니다.
여기서 특정 값(target)이 주어졌을 때, 해당 값이 배열 안에 존재하면 true, 존재하지 않으면 false를 반환하는 것이 이번 문제의 목표입니다. 예를 들어 배열이 [2,5,6,0,0,1,2]이고 target이 0이라면, 결과는 true가 됩니다.
이 문제가 일반적인 이진 탐색과 다른 점은 두 가지입니다. 첫째, 배열이 회전되어 있어 전체가 정렬 상태가 아니라는 점, 둘째, 중복된 값이 허용된다는 점입니다. 특히 중복 때문에 최악의 경우 이진 탐색의 장점이 줄어들 수 있어, 이를 처리하는 로직이 핵심입니다.
접근 방식: 변형된 이진 탐색
기본 아이디어는 다음과 같습니다. 회전된 배열을 반으로 나누면, 어느 한쪽 절반은 반드시 정렬되어 있습니다. 따라서 각 단계에서 정렬된 쪽 범위에 target이 속하는지 확인하고, 속한다면 그쪽으로 탐색 범위를 좁히고, 속하지 않는다면 반대쪽으로 좁히면 됩니다. 다만 양 끝의 값과 mid 값이 모두 같은 경우에는 어느 쪽이 정렬된 상태인지 판단할 수 없으므로, 탐색 범위를 한 칸씩 줄여가며 중복을 제거해야 합니다.
알고리즘 단계
- 포인터를 초기화합니다:
low = 0,high = 배열의 길이 low < high인 동안 반복합니다:mid = low + (high - low) / 2를 계산합니다.nums[mid] == target이면 true를 반환합니다.nums[low] == nums[mid]이고nums[high - 1] == nums[mid]이면 어느 쪽이 정렬되었는지 알 수 없으므로,low를 1 증가시키고high를 1 감소시킨 뒤 다음 반복으로 넘어갑니다(중복 제거).nums[low] <= nums[mid]라면 왼쪽 절반이 정렬된 상태입니다. 이때target >= nums[low]이고target < nums[mid]이면high = mid로 설정하고, 그렇지 않으면low = mid + 1로 설정합니다.- 그 외의 경우 오른쪽 절반이 정렬된 상태입니다.
target <= nums[high - 1]이고target > nums[mid]이면low = mid + 1로 설정하고, 그렇지 않으면high = mid로 설정합니다.
- 반복문이 끝나면 값을 찾지 못한 것이므로 false를 반환합니다.
구현 예시
먼저 문제 제목에 맞춰 C++ 구현을 살펴보겠습니다.
#include <vector>
using namespace std;
class Solution {
public:
bool search(vector<int>& nums, int target) {
int low = 0;
int high = nums.size();
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target)
return true;
// 양 끝과 mid가 모두 같으면 정렬 방향을 판단할 수 없음
if (nums[low] == nums[mid] && nums[high - 1] == nums[mid]) {
low++;
high--;
continue;
}
if (nums[low] <= nums[mid]) { // 왼쪽 절반이 정렬됨
if (target >= nums[low] && target < nums[mid])
high = mid;
else
low = mid + 1;
} else { // 오른쪽 절반이 정렬됨
if (target <= nums[high - 1] && target > nums[mid])
low = mid + 1;
else
high = mid;
}
}
return false;
}
};참고로 원본 글의 예시 코드(Python)는 들여쓰기 오류로 인해 동작하지 않는 형태였는데, 이를 올바르게 수정하면 다음과 같습니다.
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
low = 0
high = len(nums)
while low < high:
mid = low + (high - low) // 2
if nums[mid] == target:
return True
if nums[low] == nums[mid] and nums[high - 1] == nums[mid]:
low += 1
high -= 1
continue
if nums[low] <= nums[mid]:
if target >= nums[low] and target < nums[mid]:
high = mid
else:
low = mid + 1
else:
if target <= nums[high - 1] and target > nums[mid]:
low = mid + 1
else:
high = mid
return False입력 및 출력 예시
입력
nums = [2,5,6,0,0,1,2] target = 0
출력
true
배열 내에 0이 실제로 존재하므로 함수는 true를 반환합니다. 만약 target이 3이라면 배열에 없는 값이므로 false가 출력됩니다.
복잡도 분석
- 시간 복잡도: 평균적으로 O(log n)입니다. 다만 중복 값이 많은 최악의 경우(예: 모든 원소가 같은 배열)에는 매 반복마다 탐색 범위가 1씩만 줄어들어 O(n)까지 늘어날 수 있습니다.
- 공간 복잡도: 추가 자료구조를 사용하지 않는 제자리(in-place) 알고리즘이므로 O(1)입니다.
마무리
이 문제는 LeetCode 81번 'Search in Rotated Sorted Array II'와 동일한 유형으로, 회전된 정렬 배열에서의 이진 탐색(LeetCode 33번)에서 중복 처리 조건 하나가 추가된 형태입니다. 중복이 없는 버전에 익숙하다면, nums[low] == nums[mid]와 nums[high - 1] == nums[mid]가 동시에 성립할 때 경계를 좁혀주는 부분만 잘 이해하면 쉽게 확장할 수 있습니다.