Leetcode - 33. Search in Rotated Sorted Array

문제

Loading...

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCode

풀이

아이디어는 리스트가 rotated 되어 있으면, pivot을 찾은 다음 좌/우에서만 이진검색을 실행하는 것이다.

하지만 테스트 케이스 중 [1,3,5] 때문에 이 풀이는 틀렸다. 문제에서 모든 입력 리스트는 rotated 되어 있다고 해서 이렇게 풀었는데..

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Find pivot
        left, right = 0, len(nums)-1
        while left < right:
            mid = (left + right) // 2
            
            if nums[mid] > nums[right]:
                # 4, 5, 6, "7", 0, 1, "2"
                left = mid + 1
            else:
                # 6, 7, 0, "1", 2, 4, "5"
                right = mid
                
        pivot = left
        
        # Bisect
        print(pivot)
        if target >= nums[0]:
            return self.binary_search(target, nums[:pivot])
        else:
            res = self.binary_search(target, nums[pivot:])
            return pivot + res if res != -1 else -1
    
    @staticmethod
    def binary_search(target, candidates):
        left, right = 0, len(candidates)-1
        while left <= right:
            mid = (left + right) // 2
            
            if candidates[mid] < target:
                left = mid + 1
            elif candidates[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

신기한 풀이. target과 mid가 0번 인덱스 기준으로 "같은 리스트" 안에 있으면 이진검색을 실행한다.

class Solution:
    def search(self, nums, target):
        lo, hi = 0, len(nums)

        while lo < hi:
            mid = (lo + hi) // 2

            if (nums[mid] < nums[0]) == (target < nums[0]):
                if nums[mid] < target:
                    lo = mid + 1
                elif nums[mid] > target:
                    hi = mid
                else:
                    return mid
            elif target < nums[0]:
                lo = mid + 1
            else:
                hi = mid

        return -1