회전 정렬된 배열에서 검색

오름차순(개별 값 포함)으로 정렬된 정수 배열nums이 있습니다.

함수에 전달되기 전에 nums는 알 수 없는 피벗 인덱스k(1 <= k < nums.length)에서 회전하여 결과 배열이 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]](인덱스 0)가 될 수 있습니다. 예를 들어 [0,1,2,4,5,6,7]는 피벗 인덱스 3에서 회전하여 [4,5,6,7,0,1,2]가 될 수 있습니다.

가능한 회전 후 배열 nums 및 정수 target 가 주어지면 target 에 있는 경우 nums 의 인덱스를 반환하고 -1 에 없는 경우 nums 의 인덱스를 반환합니다.

런타임 복잡도O(log n)로 알고리즘을 작성해야 합니다.

예 1:

입력: 숫자 = [4,5,6,7,0,1,2], 대상 = 0
출력: 4

예 2:

입력: 숫자 = [4,5,6,7,0,1,2], 대상 = 3
출력: -1

예 3:

입력: 숫자 = [1], 대상 = 0
출력: -1

제약:

1 <= nums.length <= 5000

-104 <= nums[i] <= 104

nums의 모든 값은 고유합니다.

nums는 회전 가능한 오름차순 배열입니다.

-104 <= target <= 104

해결책:

class Solution:
    def getPivot(self, nums):
        n = len(nums)
        beg = 0
        end = n
        while beg <= end:
            mid = (beg + end) // 2
            if mid < n - 1 and nums[mid] > nums[mid + 1]:
                return mid + 1
            if beg >= end - 1:
                return 0
            elif nums[mid] > nums[0]:
                beg = mid
            else:
                end = mid

    def binarySearch(self, nums, beg, end, target):
        while beg <= end:
            mid = (beg + end) // 2
            if mid >= end:
                break
            elif nums[mid] == target:
                return mid
            elif beg == end:
                break
            elif nums[mid] > target:
                end = mid
            else:
                beg = mid + 1
        return -1

    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        k = self.getPivot(nums)
        left = self.binarySearch(nums, 0, k, target)
        if left != -1:
            return left
        right = self.binarySearch(nums, k, n, target)
        if right != -1:
            return right
        return -1