[Leetcode] 81. Search in Rotated Sorted Array II

Problem:

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= 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,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

 

Example 1:

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

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
 

Constraints:

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums is guaranteed to be rotated at some pivot.
-104 <= target <= 104

 

나는 이문제를 풀지 못했다. Claude3 Solution을 제출했다. 

Solution1:

from typing import List

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

        while left <= right:
            mid = left + (right - left) // 2

            # If the middle element is the target, return True
            if nums[mid] == target:
                return True

            # If the left half is sorted or the elements are duplicates
            if nums[left] == nums[mid]:
                left += 1
            elif nums[left] <= nums[mid]:
                # If the target is in the left half
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1

            # If the right half is sorted or the elements are duplicates
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return False

위 solution은 Claude3가 작성한 Solution이다. 코드를 리뷰해 보자면, pivot을 따로 찾지 않고, 바로 실전에 투입한다. 

target값이 같으면 True를 리턴한다. 같지 않다면 크게 세가지로 나뉜다. nums [left]와 nums [mid]와의 비교다. 같다, 크다, 작다로 나뉜다. nums [left]와 nums [mid]를 비교하는 이유는 pivot이라는 변수가 존재하기 때문이다. 따라서, nums가 오름차순이 아닌 리스트라는 이야기다. 따라서, nums [mid] == nums [left]라면 left = mid + 1로 바꾼다. 그 이유는 nums [mid]와 nums [left] 사이에는 똑같은 값만 존재한다는 뜻이고, if nums [mid] == target이 아니기에, 그렇게 생각할 수 있다. 

 

다음으로 , nums[left] < nums [mid]일 때이다. 이 경우는 오름차순을 유지한다고 볼 수 있다. 따라서, 이 경우 또 두 가지로 나누어 생각할 수 있다. 첫 번째 , target 이 nums [left]와 nums [mid] 사이에 있을 때이다. 이때는 right값을 mid - 1로 수정한다. 다른 경우는 left + 1로 수정한다. 

 

마지막으로, nums[left] > nums [mid]일 때이다. 이 경우는 left와 mid 사이에 pivot값으로 인한 오름차순이 유지되고 있지 않음을 뜻한다. 따라서, 경우의 수를 나눠야 한다. nums [mid]와 nums [right] 사이에 값이 있을 때는, left = mid + 1로 수정한다. 그렇지 않은 경우는 right = mid - 1로 수정한다.