LeetCode 33. Search in Rotated Sorted Array

파이썬 알고리즘 인터뷰 66번(리트코드 33) Search in Rotated Sorted Array
https://leetcode.com/problems/search-in-rotated-sorted-array/

나의 풀이

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif nums[left] <= nums[mid]: # 왼쪽이 제대로 정렬
                if nums[left] <= target <= nums[mid]: # 왼쪽을 탐색
                    right = mid - 1
                else: # 오른쪽을 탐색
                    left = mid + 1
            else: # 오른쪽이 제대로 정렬
                if nums[mid] <= target <= nums[right]: # 오른쪽을 탐색
                    left = mid + 1
                else: # 왼쪽을 탐색
                    right = mid - 1
        return -1

• 절반 쪼개어 둘 중 제대로 정렬된 부분을 찾는다.
• 그리고 원하는 값이 둘 중 어느 부분에 있는 지 판단하는 것을 반복한다.

다른 풀이

class Solution:
    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

• 먼저 값이 감소하는 부분, 그러니까 pivot을 찾는다.
• 그 다음 절반을 계산할 때 left, right의 절반으로 구한 후 pivot을 더하여 보정한 절반을 이용한다.