[Leetcode/파이썬] 33. Search in Rotated Sorted Array

Search in Rotated Sorted Array

---

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

 

Constraints:

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -104 <= target <= 104

 

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

이 문제를 왜 이분탐색으로 풀어야할까... 기본적으로 정렬되어 있는 숫자 배열을 왼쪽으로 밀어넣은 배열을 가지고 있다. 그냥 보고 있으면 정렬이 되어 있지 않기 때문에 그냥 하나씩 넘어가면서 보는게 낫지 않을까 싶었는데 여지없이 $O(logN)$으로 문제를 해결하라고 한다. 

이 문제를 한 번에 풀지는 못했는데, 이는 이분탐색을 어떻게 적용해야 할지 몰라서 였다. 처음으로 돌아가서 이분탐색은 해당 범위 내에 값이 없을 거라고 판단되면 그 범위는 바로 버리는 탐색이다. 이 문제는 이러한 특성을 어떻게 하면 꼬아서 표현할 수 있을지에 대해서 문제를 내어놓았다. 

코드를 살펴보자. 기본적으로 이분탐색은 중간 지점을 기점으로 해당 값이 어디에 위치해있을지에 대해 찾는 알고리즘이다. 그렇기 때문에 중간값을 찾고 중간값이 타겟이 아니라면 이제부터 본격적인 게임이 시작된다. 중간 값이 가장 왼쪽의 값보다 클 경우, 우리는 이 범위에서는 정렬된 배열이라고 생각할 수 있다. 문제에서 주어진 배열은 정렬된 배열에서 왼쪽으로 N번 돌린 배열이라고 제한 하였기 때문에 왼쪽값이 가장 작은 값이라고 생각한다면, 중간값이 왼쪽값보다 클 경우 우리는 왼쪽에서 중간까지는 정렬된 배열이라고 생각할 수 있다. 이 정렬된 배열에서 타겟값이 존재하는지 찾고 만약 존재한다면 오른쪽 인덱스를 중간값 - 1으로 이동시킨다. 이 과정을 잘 펴보면 될 것이다. 

나는 1번 테스트 케이스를 숫자만 몇개씩 바꿔가며 테스트 돌린 결과 이해할 수 있었으니, 혹시나 이해가 잘 되지 않는다면 값을 변경해보길 바란다. 리트코드의 장점이 테스트 케이스만 집어 넣으면 결과값을 알아서 주기 때문에 다른 코딩 테스트를 보는 저지 사이트들 보다는 초보자가 빨리 성장하기 좋다. 

테스트 케이스 1번을 예시로 들어보면

• nums[mid] = 7, target 이 아니다.
  • nums[mid] > nums[left] 이므로 if 문을 수행한다.
  • 그러나 target 이 해당 범위 내에 없기 때문에 left = mid + 1 로 left = 4가 된다.
  • => left = 4, right = 6
• nums[mid] = 1, target 이 아니다.
  • nums[mid] > nums[left] 이므로 if 문을 수행한다.
  • target == nums[left] 이므로 right = mid - 1 로 이동한다.
  • => left = 4, right = 4
• nums[mid] = 0, target 이다. return

이런 식으로 돌아갈텐데, 나중에 그림으로 직접 그려봐도 좋을 것 같다.