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

🤔 문제

---

Search in Rotated Sorted Array - LeetCode

 

😀 풀이

---

해당 문제는 이진 탐색을 조금 더 응용하여 풀이할 수 있는 문제입니다. 특정 인덱스를 기준으로 rotate 되어 기존 방식으로 이진 탐색을 하는 것이 불가능하여 한 단계 더 과정을 거쳐야 문제 조건에 맞게 풀이할 수 있습니다. 

 

가장 처음 생각한 방법은 다음과 같습니다.

1.  rotate가 몇 번 되었는지 확인한다. 즉, 배열에서 가장 작은 값의 위치를 찾는다.
2. 해당 인덱스를 기준으로 좌측과 우측은 정렬되어 있는 상태이므로 이를 대상으로 각각 이진탐색을 한다.
3. 좌, 우측의 이진 탐색의 결과로 답을 구한다.

위 방법이 아래 전체 코드에서 나올 풀이 1에 해당합니다. 코드를 부분적으로 살펴보겠습니다.

# 배열에서 가장 작은 값이 어디있는지 이진 탐색
def find_smallest_num_index(nums):
    left, right = 0, len(nums) - 1

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

위 코드를 통해 배열에서 가장 작은 값의 인덱스를 이진탐색 방식으로 찾을 수 있게 되고 이는 곧 rotate가 몇 번 되었는지에 대한 정보를 줍니다.

 

해당 인덱스를 기준으로 좌측과 우측은 정렬되어있으므로 기존에 알고 있던 이진 탐색을 사용할 수 있게 됩니다. 따라서 좌측과 우측 각각 이진 탐색을 통해 target을 검색하면 정답을 구할 수 있습니다.

 

여기까지가,, 가장 처음 생각했던 풀이 방법입니다.

 

하지만 rotate된 횟수를 offset으로 사용하여 이진탐색을이진 탐색을 한다면 좌, 우측으로 나누어 두 번 이진 탐색을 하지 않고 한 번의 이진탐색으로도 정답을 구할 수 있습니다.

 

해당 부분 코드는 아래와 같습니다.

pivot = find_smallest_num_index(nums)

left, right = 0, len(nums) - 1

while left <= right:
    mid = (left + right) // 2
    mid_with_offset = (mid + pivot) % len(nums)

    if nums[mid_with_offset] == target:
        return mid_with_offset
    elif nums[mid_with_offset] > target:
        right = mid - 1
    else:
        left = mid + 1
return -1

mid_with_offset이라는 mid 값에 pivot 만큼 offset을 준 변수를 통해 마치 배열이 회전되기 전의 모습을 가지고 이진 탐색을 하는 것과 같은 효과를 낼 수 있습니다! LeetCode 제출 결과를 보면 runtime이 반절 가량 줄어든 모습을 볼 수 있죠.

 

 

---

💻 전체 풀이 코드는 아래와 같습니다.

풀이1 - 좌, 우측에 대해 각각 이진 탐색을 적용하는 방식

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

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

        def binary_search(arr, _target):
            left, right = 0, len(arr) - 1

            while left <= right:
                mid = (left + right) // 2
                if arr[mid] == _target:
                    return mid
                elif arr[mid] > _target:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1

        smallest_num_index = find_smallest_num_index(nums)


        left_nums = nums[:smallest_num_index]
        right_nums = nums[smallest_num_index:]

        left_idx = binary_search(left_nums, target)
        right_idx = binary_search(right_nums, target)


        if left_idx != -1:
            return left_idx
        if right_idx != -1:
            return right_idx + smallest_num_index
        return -1

---

풀이2 - Offset을 통해 이진 탐색을 한 번만 하는 좀 더 효율적인 방식

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

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

        pivot = find_smallest_num_index(nums)

        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            mid_with_offset = (mid + pivot) % len(nums)

            if nums[mid_with_offset] == target:
                return mid_with_offset
            elif nums[mid_with_offset] > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1