[Leetcode] 33. Search in Rotated Sorted Array

Problem 

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.

 

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:

Input: nums = [1], target = 0
Output: -1
 

Constraints:

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104

 

이 문제를 나는 풀지 못했다. 다른 solution을 참고하여 나의 답을 작성하였다. 

solution:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right = 0, len(nums) - 1 
        mid = 0 
        while left <= right: 
            mid = (left + right) // 2 
            if target == nums[mid]:
                return mid 
            if 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

이렇게 풀어보니, 썩 좋은 성능을 발휘하지 못했다. 코드를 간단하게 리뷰해 보자

 이 문제의 핵심은 Binary search를 이용하는 거다. 하지만 이 문제에서는 pivot이라는 변수를 주어, 오름차순의 흐름이 끊긴다. 이렇게 될 경우, Binary Search를 정상적으로 사용하지 못한다. 따라서, 오름차순이 끊기는 지점을 찾아 case를 분류하여야 한다. 위 코드에서 if nums [left] <= nums [mid]라는 조건을 달아, 오름차순이 끊기는지 확인 후 기존 Binary Search를 적용하고 있다. 하지만, 이 경우는 [4,5,6,7,0,1,2]라는 nums가 있을 때, 처음 mid부터 시작하여 메모리를 차지 많이 한다. 

따라서, 성능면에서 좋지 못했다. 

 

내가 참고한 solution 2:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def searchPivot():
            # pivot: search space[0, n - 1]
            # before pivot, element > last one
            # after pivot, element <= last one
            # find the min value of i let nums[i] <= nums[-1]
            n = len(nums)
            left, right = 0, n - 1
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] <= nums[-1]:
                    right = mid
                elif nums[mid] > nums[-1]:
                    left = mid + 1
            return left

        def binarySearch(left, right):
            # binary search
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    return mid
            return -1
        pivot = searchPivot()
        if target > nums[-1]:
            return binarySearch(0, pivot - 1)
        else:
            return binarySearch(pivot, len(nums) - 1)

위 solution을 간단하게 요약하면, pivot을 미리 찾고, pivot을 기준으로 binary search를 수행한다. 즉 , solution 1에서의 불필요한 과정들을 pivot을 찾음으로 인해 간소화하였다. 메모리 이용을 줄이는 아이디어였던 것이다.