LC 33. Search In Rotated Sorted Array

문제 개요

• 정렬된 배열을 회전시켰을 때 그 안에 target 값이 있는지 판단하는 문제.

• 경우의 수가 많아지니 포인터 움직이는게 정말 헷갈렸다.

• 이 문제의 핵심은 6가지 경우의 수를 잘 탐색하는 것!

정렬된 배열을 회전시켰다는 건 두 부분으로 정렬된 값들이 나눠진다는 것을 의미한다.

풀이 구상

• 왼쪽 정렬된 부분, 오른쪽 정렬된 부분으로 나뉘는 조건을 찾는다.

• 각 부분에서 target 값이 왼쪽에 있을 수 있고 오른쪽에 있을 수 있다.

• 총 6가지 경우의 수를 차근차근 분기처리 해준다.

문제해결 코드

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # target이 nums 안에 있으면 target의 인덱스 리턴, 없으면 -1 리턴
        l, r = 0, len(nums) - 1

        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m

            # 왼쪽 정렬된 배열
            if nums[l] <= nums[m]:
                if target > nums[m] or target < nums[l]:
                    l = m + 1
                else:
                    r = m - 1
                    
            # 오른쪽 정렬된 배열
            else:
                if target < nums[m] or nums[r] < target:
                    r = m - 1
                else:
                    l = m + 1
        return -1

• 시간복잡도: 이진탐색을 적용했기 때문에 O(logn)