문제 설명
오름차순으로 정렬된 배열이 있고, 이 배열이 미리 알 수 없는 임의의 피벗(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]이고 목표값이 0이라면 결과는 True가 됩니다.
알고리즘 접근 방식
이 문제는 수정된 이진 탐색(binary search)으로 해결할 수 있습니다. 일반적인 이진 탐색과 달리 배열에 중복 값이 존재하기 때문에, nums[low], nums[mid], nums[high-1] 세 값이 모두 같은 경우 어느 쪽 절반이 정렬되어 있는지 판단할 수 없습니다. 따라서 이런 경우 탐색 범위 양 끝을 한 칸씩 좁혀가며 모호성을 제거하는 것이 핵심입니다.
구체적인 단계는 다음과 같습니다.
- low := 0, high := 배열의 크기로 초기화합니다.
- low < high인 동안 아래 과정을 반복합니다.
- mid := low + (high - low) / 2 로 중간 인덱스를 계산합니다.
- nums[mid]가 목표값과 같으면 true를 반환합니다.
- nums[low] = nums[mid]이고 nums[high - 1] = nums[mid]라면, low를 1 증가시키고 high를 1 감소시킨 뒤 다음 반복으로 넘어갑니다.
- nums[low] <= nums[mid]라면 왼쪽 절반이 정렬된 상태입니다.
- 목표값이 nums[low] 이상이고 nums[mid] 미만이면 high := mid로 설정하고, 그렇지 않으면 low := mid + 1로 설정합니다.
- 그 외의 경우 오른쪽 절반이 정렬된 상태입니다.
- 목표값이 nums[high - 1] 이하이고 nums[mid]보다 크면 low := mid + 1로 설정하고, 그렇지 않으면 high := mid로 설정합니다.
- 반복이 끝나면 false를 반환합니다.
구현 예제
class Solution(object):
def search(self, nums, target):
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
ob1 = Solution()
print(ob1.search([2,5,6,0,0,1,2], 0))입력
[2,5,6,0,0,1,2] 0
출력
True
시간 복잡도 분석
배열 내 중복 값이 적다면 평균적으로 O(log n)의 시간 복잡도로 동작합니다. 하지만 모든 요소가 같은 값인 최악의 경우에는 매 반복마다 탐색 범위가 1씩만 줄어들어 O(n)까지 증가할 수 있습니다. 공간 복잡도는 추가 메모리를 사용하지 않으므로 O(1)입니다.