LeetCode 33(Search in Rotated Sorted Array, Python)

1. 문제 링크

• https://leetcode.com/problems/search-in-rotated-sorted-array/

Search in Rotated Sorted Array - LeetCode

2. 문제 설명

• 기존에 오름차순으로 정렬된 배열을 특정 기준점(피벗)에서 회전시킨 배열에서 특정 값(target)을 찾는 문제
• 예시) [0,1,2,4,5,6,7]을 회전한 nums = [4,5,6,7,0,1,2]에 대해 target = 0이면 4를 반환

3. 처음 풀이

• 01234 같은 경우 회전되지 않았으므로 제일 처음이 마지막보다 작다.
• 34012 같은 경우 회전되었으므로 제일 처음이 마지막보다 크다.
• 따라서 우선 처음과 마지막을 비교하여 회전이 되었는지, 아닌 지 판단할 수 있고, 회전되지 않았다면 일반적인 이진검색을 할 수 있음.
• 회전된 경우 오름차순이 안되는 경곗값 index를 찾을 것이다.
• 예시: 34012
• 양끝 index를 l, r로 잡고 m=(l+r)//2로 정하여 가운데 값을 보면 0이다.
• 왼쪽 절반 양끝은 3, 0으로 역순이고 오른쪽 절반 양끝은 0, 2로 정상 순서이다. 정상 부분을 날리고 왼쪽 절반 340을 본다.
• 왼쪽 절반 양끝은 3, 4로 정상 순서이고 오른쪽 절반 양끝은 4, 0으로 역순이다. 정상 부분을 날리고 오른쪽 절반 40을 본다.
• 이제 l = m 이 되었으므로 m을 리턴하면 4의 index인 1이 return 되며, 이 값이 pivot=1이다. index가 1에서 2로 넘어갈 때 역순이 일어난다.
• pivot값을 이용하여 정상적으로 오름차순 정렬된 리스트 temp=nums[pivot+1:] + nums[:pivot+1] 를 생성한다.
• 이제 오름차순이므로 일반적인 이진 검색을 한 후 index를 pivot값 이용해서 조정해준다.

class Solution:
    def search(self, nums: List[int], target: int) -> int:

        # 회전된 배열에서 pivot(회전의 기준이 되는 인덱스)을 찾는 함수
        def find_pivot(nums):
            l, r = 0 , len(nums)-1
            m = (l+r)//2
            while l < m:
                if nums[l] > nums[m]:
                    r = m
                    m = (l+r)//2
                elif nums[m] > nums[r]:
                    l = m
                    m = (l+r)//2
            return m
       
        # 정렬된 배열에서 이진 검색을 수행하는 함수
        def find_binary(nums):
            l, r = 0 , len(nums)-1
            while l < r:
                m = (l+r)//2
                if nums[m] == target:
                    return m
                elif nums[m] > target:
                    r = m-1
                    m = (l+r)//2
                else:
                    l = m+1
                    m = (l+r)//2
            if nums[l] == target:
                return l
            else:
                return -1

        # 메인 함수
        l, r = 0 , len(nums)-1
        m = (l+r)//2
        # 배열이 정렬되어 있는 경우 바로 이진 검색 수행
        if nums[0] <= nums[-1]:
            return find_binary(nums)
        # 회전된 배열인 경우 find_pivot으로 pivot을 찾아 회전을 해제하고, find_binary로 이진 검색 수행
        else:
            pivot = find_pivot(nums)
            temp = nums[pivot+1:] + nums[:pivot+1]
            index = find_binary(temp)
            # 찾은 결과에 따라 인덱스를 조정하여 반환
            if index == -1:
                return -1
            else: 
                result = index + pivot + 1
                if result > len(nums) - 1:
                    return result - len(nums)
                else:
                    return result

4. 다른 풀이

• 가운데 기준으로 왼쪽 절반, 오른쪽 절반 중 하나는 무조건 오름차순이다. 이를 이용하면 굳이 리스트를 오름차순으로 바꾸지 않아도 이진 검색을 할 수 있음.
• 예시: 34012, target =4
• 왼쪽 절반 340, 오른쪽 절반 012 중 오른쪽 절반이 정렬되어 있다.
• 하지만 target=4가 오른쪽 절반의 양끝인 0, 2 사이에 없으므로 target=4를 왼쪽 절반에서 찾아야 하므로 right=mid-1하여 34를 관찰한다.
• 이제 잘 정렬된 부분이니 마저 이진 검색을 수행하면 찾을 수 있음.

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

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

            if nums[mid] == target:
                return mid

            # Check if left half is sorted
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Otherwise, right half is sorted
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

5. 배운 점

• 이진 검색의 조건이 오름차순이긴 하지만 한 번 회전된 경우는 이진 검색을 할 수 있다.
• 찾는 값이 없을 수 있는 경우 이진 검색 코드가 좀 지저분하게 짰었는데 일반적인 깔끔한 코드를 알게 되었다. target 값을 못 찾은 채로 l이 r보다 커지면 while 문을 벗어나고 while 문 밖에 -1을 리턴하면 됨.