[DSA][Binary Search] 05. Search in Rotated Sorted Array

LeetCode 33

 

05. 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.

 

 

[질문하기]

- 배열에 항상 target 값이 존재하나요? NO

 

 

[아이디어]

- mid 인덱스의 값과 r 인덱스의 값을 비교하여 정렬된 구간을 찾고, 정렬된 구간에 대해 target이 있을 위치를 추적하자.

 

 

[풀이 1] Binary Search

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

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

앞선 문제에서 mid의 값과 r의 값을 비교하여 최솟값을 찾았다.

2025.06.17 - [자료구조와 알고리즘] - [DSA][Binary Search] 04. Find Minimum in Rotated Sorted Array

하지만 이 문제는 "최솟값을 찾는 문제"와는 다르게, 단순히 최솟값의 위치가 궁금한 게 아니라 특정 target 값이 배열 내에 존재하는 위치(index)를 찾는 문제이다. 따라서 nums[m], nums[r]를 비교하여 어느 구간이 정렬된 구간인지를 먼저 판단하고, 그 정렬된 구간 안에 target이 포함되는지 여부를 체크해서 탐색 범위를 좁혀 나갈 수 있다.

 

• nums[m] < nums[r]라면, 오른쪽 구간이 정렬되어 있다는 의미이고,
• 반대라면, 왼쪽 구간이 정렬되어 있다는 뜻이다.

 

 

⏱️ 시간복잡도

길이 n의 배열을 이진탐색으로 순회하므로 시간복잡도는 O(logn)이다.

🧠 공간복잡도

추가적인 공간을 사용하지 않고, 이진탐색을 위한 변수만을 사용하기 때문에 O(1)의 공간 복잡도를 갖는다.