p.525 66번 회전 정렬된 배열 검색 입력 조건과 다른 풀이

[DoTheBestMayB]

입력 조건

책 집필 당시와 문제 조건이 달라진 것 같습니다. nums의 현재 조건은 1 <= nums.length <= 5000 입니다 따라서 p.528에서 아래 코드는 지워도 될 것 같습니다.

# 예외 처리
if no nums:
    return -1

다른 풀이

nums[index] > nums[index+1] 인 pivot index를 찾고 pivot index를 기준으로 target 값이 앞 부분과 뒷 부분 중 어디에 속하는지 확인해서 탐색범위를 줄이는 방법으로 풀이해봤습니다.

책에 적힌 코드는 72ms 이고, 제가 작성한 코드는 56ms로 나옵니다. 하지만 리트코드에서 10%로 나오는데, 어떤 부분을 개선해야 할까요?

from typing import List

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

        # pivot index k가 0보다 큰 경우
        if nums[0] > nums[-1]:
            while cur_left < cur_right:
                mid = cur_left + (cur_right - cur_left) // 2
                if nums[mid] > nums[mid+1]:
                    pivot = mid
                    break
                elif nums[mid] > nums[cur_left]:
                    cur_left = mid+1
                elif nums[mid] < nums[cur_right]:
                    cur_right = mid

        # pivot을 기준으로 cur left right 다시 초기화
        if pivot != -1:
            if target > nums[pivot] or target < nums[pivot+1]:
                return -1

            if target < nums[0]:
                cur_left, cur_right = pivot+1, len(nums)-1
            elif target > nums[0]:
                cur_left, cur_right = 0, pivot
            else:
                return 0
        elif target < nums[0] or target > nums[-1]:
            return -1

        while cur_left < cur_right:
            mid = cur_left + (cur_right - cur_left) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                cur_right = mid - 1
            else:
                cur_left = mid + 1
        if cur_left > cur_right:
            return -1
        elif target == nums[cur_left]:
            return cur_left
        elif target == nums[cur_right]:
            return cur_right
        else:
            return -1

[likejazz]

안녕하세요. 말씀하신대로 예외 처리는 이제 삭제해도 될거 같습니다. 그러나 틀린 부분은 아니므로 정오표에는 반영하지 않도록 하겠습니다.

제시해주신 풀이도 좋아 보이네요. 그러나 너무 장황해서 가독성이 많이 떨어지는거 같습니다. 실행속도는 제가 해볼때는 20ms ~ 70ms 사이를 오가는거 같은데, 이 정도는 풀이의 차이 라기 보다는 리트코드의 실행속도 오차 범위로 보이며 속도는 사실상 동일하다고 봐도 될거 같습니다.