10.3 회전된 배열에서 검색

문제

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

 

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

출력  : 8 ( 배열에서 8번째 인덱스에 5가 있으므로)

 

접근법

이 문제를 보고 이진탐색을 생각했다면 매우 훌륭하다.

고전적인 이진탐색은 어떤 값 x가 왼쪽에 있는지 오른쪽에 있는지를 판단하기 위해  x를 배열의 중간 원소와 비교한다.

하지만, 이 문제는 배열이 회전된 상태라서 까다롭다. 두 배열을보자

배열 1 {10,15,20,0,5}

배열 2 {50,5,20,30,40}

이 두배열 모두 20이 가운데에 있지만, 5는 왼쪽에 있을수도 오른쪽에 있을 수도 있다.

하지만 좀더 자세히 들여다 보면, 왼쪽 또는 오른쪽은 제대로 정렬이 되어있음을 알 수 있다.

배열 1에서는 mid는 20이고 left = 10 , right =5이다. 그러면 left < mid 이므로 왼쪽은 재대로 정렬되어있음을 알 수 있다. 

하지만 왼쪽 범위안에 5가 들어갈 수 업으므로 오른쪽을 탐색해야 할 것이다.

배열 2에서는 mid는 20이고 left= 50 , right=40으로 mid < right으로 오른쪽은 제대로 정렬되어있음을 알 수 있다.

하지만 오른쪽 범위안에 5가 들어갈 수 없으므로 왼쪽을 탐색해야 할 것이다.

 

그럼 이런 경우는 어떨까?

배열 3 {2,2,2,3,5,2}

중복된 원소가 있을때는 더 까다로울 것이다. 이렇게 가운데 원소와 왼쪽 끝의 원소가 같은 경우는 어떻게 해야할까?

맨 오른쪽 원소가 같은지 확인하고 오른쪽 원소가 다르다면 오른쪽을 탐색하면 될 것이다. 

이렇게 오른쪽도 같다면 양쪽을 모두 확인해 보아야 한다. 

왼쪽을 탐색하고 답이 없다면 오른쪽도 탐색하는 방향으로 설계해야 할 것이다.

 

def Solution(nums, target):
    return serach(nums,0, len(nums)-1, target)

def serach(nums, left, right, target) :
    mid = (left+right) / 2
    if nums[mid] == target :
        return mid
    if left > right :
        return -1

    if  nums[left] < nums[mid] : # 왼쪽이 정렬된 경우
        if nums[left] <=  target and  target < nums[mid]:
            return serach(nums, left, mid-1, target)
        else :
            return serach(nums, mid+1 , right, target)
    elif nums[mid] < nums[right] :
        if nums[mid] < target and target <= nums[right]:
            return serach(nums, mid+1, right, target)
        else :
            return serach(nums, left, mid-1, target)
    elif nums[left] == nums[mid]:
        if nums[right] != nums[mid]:
            return serach(nums, mid+1, right, target)
        else :
            result = serach(nums, left, mid-1, target)
            if result == -1 :
                return serach(nums, mid+1, right, target)
            else :
                return result
    else :
        return -1