33. Search in Rotated Sorted Array

1 2 3 / 4 5 6 7 -> 4 5 6 7 1 2 3 처럼 정렬된 리스트를 일정 부분 잘라서 순서를 바꿔놓은 상태에서 원하는 값을 찾는 방법이다.

 

사실 값을 찾는 것이라 처음부터 탐색해도 되지 않을까 해서 해봤더니 Success가 뜨긴 한다. 하지만 문제의 본질은 그게 아닐테니 솔루션을 보니 '이진 탐색'을 이용하는 것이였다.

 

위처럼 Left, Mid, Right 세 인덱스 값을 이용한다.

Left =0, Right = Len(nums)-1, Mid = (Left + Right) // 2에서 시작한다.

 

두가지 경우로 나눌 수 있다. Mid값 기준으로 왼쪽이 올바르게 정렬된 경우, 그 반대의 경우.

또한 이 기준에서 또 두가지 경우로 나눌 수 있다. 숫자가 올바른 정렬에 포함된 경우, 그 반대의 경우.

 

이렇게 하면 더 빠르게 Target 숫자를 찾을 수 있다.

 

코드는 간단하지만, 두가지 경우로 나눠서 푼다는 생각은 나에게는 떠올리기 어려웠다.

 

참고 동영상

Search in rotated sorted array - Python - YouTube

 

소스 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1

        while True: 
            mid = (left + right) // 2
            if target == nums[mid]:
                return mid
            if left == right:
                return -1
            if nums[left] <= nums[mid]:
                if target > nums[mid] or target < nums[left]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                if target < nums[mid] or target > nums[right]:
                    right = mid - 1
                else:
                    left = mid + 1