회전된 배열에서의 검색 (이진 탐색)

 n개의 정수로 구성된 정렬 상태의 배열을 임의의 횟수만큼 회전시켜 얻은 배열이 입력으로 주어진다고 하자. 이 배열에서 특정한 원소를 찾는 코드를 작성하라. 회전시키기 전, 원래 배열은 오름차순으로 정렬되어있었다고 가정한다.

 

예제)

입력: {15,16,19,20,25,1,3,4,5,7,10,14}

출력: 8 (배열에서 5가 위치한 인덱스)

 

 고전적인 이진 탐색은 어떤 값 x가 왼쪽에 있는지 아니면 오른쪽에 있는지 판단하기 위해 x를 배열의 중간 원소와 비교한다. 하지만 이 문제는, 배열이 회전된 상태라서 까다롭다. 가령, 다음의 두 배열을 살펴보자.

 

배열1 : [10, 15, 20, 0, 5]

배열2: [50, 5, 20, 30, 40]

 

 이 두 배열이 모두 20이 중간에 있지만, 5는 왼쪽에 있을 수도 있고 오른쪽에 있을 수도 있다. 그러므로 가운데 원소와 x를 비교하는 것만으로는 충분하지 않다. 하지만 좀 더 자세히 들여다 보면 배열의 반은 정상적인 순서 (오름차순)로 배열되어 있다는 것을 알 수 있다. 그러므로 정상적으로 나열된 부분을 살펴보면 배열의 왼쪽 절반을 탐색해야 하는지 오른쪽 절반을 탐색해야 하는지 결정할 수 있다.

 예를 들어 배열1에서 5를 찾을 때는 맨 왼쪽 원소(10)과 가운데 원소(20)를 비교한다. 10 < 20 이므로 왼쪽 절반은 정상 순서다. 그런다 5는 그 범위 안에 있지 않으므로, 오른쪽을 탐색해야한다고 판단할 수 있다. 배열2의 경우 50 > 20이므로, 오른쪽 절반은 정상 순서로 정렬되어 있다. 그런데 5는 가운데 원소(20)와 맨 오른쪽 원소(40) 사이에 있지 않으므로, 왼쪽 절반을 탐색해야 한다.

 [2, 2, 2, 3, 4, 2]에서처럼 가운데 원소와 맨 왼쪽 원소의 값이 같은 경우에는 어떻게 할까? 이 경우엔 맨 오른쪽 원소의 값이 다른지를 살펴서, 다르다면 오른쪽 절반을 탐색하고, 아니라면 양쪽을 전부 탐색하는 수밖에 없다.

 

def search(self, nums: 'List[int]', target: 'int') -> 'bool':
        
        if not nums :
            return False
        
        l, r = 0, len(nums)-1
        
        while l < r :
            
            mid = (l+r)//2
            
            if nums[mid] == target :
                return True
            
            # 왼쪽 정렬.
            if nums[l] < nums[mid] :
                if nums[l]<=target<nums[mid]:
                    r = mid
                else :
                    l = mid+1
            # 오른쪽 정렬.        
            elif nums[l] > nums[mid] :
                if nums[mid] < target <= nums[r]:
                    l = mid+1
                else :
                    r = mid
            else :
                l += 1
                
        return nums[l] == target

 

중복된 원소가 없다고 했을 때 이 코드는 \(O(logn)\)에 동작한다. 하지만 중복된 원소가 많을 때는 \(O(n)\)이 소요된다. 중복된 원소가 많다면 배열의 양쪽 모두 탐색해야 할 경우가 많기 때문이다.

 

출처 :게일 라크만 맥도웰. Cracking the coding interview. 프로그래밍 인사이트.