[리트코드(LeetCode)] 33 Search in Rotated Sorted Array

 

Search in Rotated Sorted Array - LeetCode

 

- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. - 

 

 

풀이

특정 피벗을 기준으로 회전하여 정렬된 배열로, 완전하게 정렬이 되어 있지 않아 일반적인 이진 탐색을 그대로 활용하기는 어려웠음.

먼저 피벗을 찾고, 배열이 피벗값만큼 회전되었음을 고려하여 이진 탐색을 적용하는 순서를 문제를 도출해야 했다.

 

피벗을 찾는 방법은 여러 가지가 있지만, 예시 입력 배열을 보면 알 수 있듯이 배열에서 가장 작은 값을 가진 인덱스가 피벗이 된다.

pivot = nums.index(min(nums))

 

파이썬에서는 위와 같이 피벗을 쉽게 구할 수도 있겠지만, 이진 탐색을 학습하는 중에 있기 때문에 이진 탐색을 활용하여 피벗을 구한다.

 

left, right = 0, len(nums) - 1
while left < right:
	mid = left + (right - left) // 2  # 자료형을 초과하지 않는 중앙 위치 계산
	
    if nums[mid] > nums[right]:
    	left = mid + 1
    else:
    	right = mid
        
pivot = left

 

 

책을 토대로 학습을 하면서 새롭게 알게 된 사실!

 

이진 탐색을 구현할 때 중앙값을 구할 때 mid = (left + right) / 2 와 같은 수식으로 구하는데, 이렇게 구현하면 버그가 발생할 수 있다고 한다. left + right 값이 int형일 때 범위를 넘어서게 되는 경우가 이에 해당하는데, 결과 값이 int 자료형이 허용하는 최댓값을 초과하기 때문에 오버플로우가 발생할 수 있다고 한다.

 

대신, mid = left + (right - left) / 2 와 같은 수식을 사용하면 해당 버그를 해결할 수 있다.

(파이썬은 임의 정밀도 정수형을 지원하기 때문에, 이 문제에 해당 사항이 없다.)

 

 

피벗 값을 찾았다면, 이제는 다시 이진 검색을 통해 target 값의 인덱스를 찾아낸다.

 

이진 탐색 시,

타겟과 값을 비교하는 부분은 mid가 아닌 아래의 수식으로 도출된 mid_pivot을 기준으로 하고, 

left와 right는 mid를 기준으로 움직이도록 한다.

mid_pivot = (mid + pivot) % len(nums)

mid_pivot은 중앙의 위치 mid에 pivot만큼 이동하고, 배열의 길이를 초과할 경우 다시 앞으로 회전할 수 있도록 처리한다.

 

 

 

코드

# 리트코드 33. Search in Rotated Sorted Array

from typing import List


class Solution:
    # 풀이 1. 피벗을 기준으로 한 이진 검색
    def search(self, nums: List[int], target: int) -> int:
        # 예외 처리
        if not nums:
            return -1

        # 최솟값을 찾아 피벗 설정
        left, right = 0, len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2  # 자료형을 초과하지 않는 중앙 위치 계산

            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        pivot = left

        # 피벗 기준 이진 검색
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            mid_pivot = (mid + pivot) % len(nums)

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

        return -1

 

파이썬 알고리즘 인터뷰 - 교보문고