[leetcode] 33. Search in Rotated Sorted Array

문제 설명

링크
정렬된 배열이 k 번째 인덱스에서 회전되었을 때, 특정 원소의 위치를 O(log(n)) 만에 구하는 문제

접근 1 - 회전이 시작된 인덱스구하기

• 회전이 시작된 인덱스 (오름차순이 위배되는 곳) 을 찾아서 l, r 정하기
• 인덱스를 찾느라 O(n) 의 시간이 소요될 수 있음

코드 1

    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l = k = 0; r = n - 1

        while k < n - 1 and nums[k] <= nums[k + 1]:
            k += 1
        if k == n - 1:
            l = 0; r = n -1
        elif target > nums[-1]:
            r = k
        else:
            l = k + 1

        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid -1
        return -1

접근 2 - Binary Search 변형

• mid 값이 l 보다 크다면 > 왼쪽이 정렬되어 있으므로 왼쪽 부분에 대해서 binary search 조건 달기 (ex. 4, 5, 6, 7, 1, 2 mid = 7 이므로 4, 5, 6, 7 에서 수행 가능)
• mid 값이 l 보다 작다면 > 오른쪽이 정렬되어 있으므로 오른쪽 부분에 대해서 binary search
• 더 빠름

코드 2

    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        l = k = 0; r = n - 1

        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < nums[l]:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
            else:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
        return -1