LeetCode - 33. Search in Rotated Sorted Array [Python]

https://leetcode.com/problems/search-in-rotated-sorted-array/

Search in Rotated Sorted Array - LeetCode

---

풀이 과정

오름차순으로 정렬된 배열이 회전되어져서 주어질 때, target값의 인덱스를 O(logN)으로 구하는 문제이다. 없으면 -1을 리턴하면 된다.

 

O(logN)으로 구해야 하므로 배열을 전부 살펴보며 target값이 있는지 확인하는 O(N) 방법은 사용할 수 없다. 몇번 회전되어 있는지를 구하고 다시 회전시키고 이진 탐색을 수행하면 좋을 것 같은데 몇번 회전되어 있는지를 구하는 연산도 O(N)이다... 이런....

 

0 1 2 3 4 5 6 이라는 배열을 생각해보자. 이 배열을 회전시키면

 

        mid

0 1 2 3 4 5 6

1 2 3 4 5 6 0

2 3 4 5 6 0 1

3 4 5 6 0 1 2

4 5 6 0 1 2 3

5 6 0 1 2 3 4

6 0 1 2 3 4 5

 

이다. 처음 값을 left로 두고 마지막 값을 right로 두고 while left <= right으로 이진 탐색을 수행한다고 할 때 다음과 같은 생각을 할 수 있다.

 

nums[left] < nums[mid]가 성립한다면? 일단 left ~ mid까지는 정렬이 되어있다는 소리고 (중간에 대소관계의 역전이 발생하지 않음) 그 안에서는 이진 탐색을 수행할 수 있을 것이다.

 

nums[left] < nums[mid]가 성립하지 않는다면? nums[mid] < nums[right]는 무조건 성립하고 그 안에서는 이진 탐색을 수행할 수 있다. 0 1 2 3 4 5 6 을 회전시킨 배열들을 보면서 대입해보면 이해가 편리하다.

 

nums[left] < nums[mid]가 성립했다면? nums[left] <= target <= nums[mid]인지 체크해서 왼쪽 배열에 target값이 존재하는지 판단할 수 있다. 없으면 오른쪽 배열에 있을 가능성이 있으므로 오른쪽을 찾아봐야 한다.

 

이와 유사한 논리로 왼쪽 정렬되어 있는데 왼쪽에 있는 경우, 없는 경우 그리고 오른쪽이 정렬되어 있는데 오른쪽에 있는 경우, 없는 경우... 이렇게 모두 따져보면 이진 탐색이 가능함을 알 수 있다.

---

소스 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        mid = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1