문제

• 오름차순으로 정렬된 중복 없는 array nums
• rotate 된 채로 주어짐
• traget의 현 위치 리턴
• 어레이에 target 없으면 -1 리턴
• O(logn)으로 해결

풀이

• 바이너리 써치 해야겠지..?

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        N = len(nums)
        return binarySearch(0, N, nums, target)

def binarySearch(start, end, nums, target):
    if end - start < 2:
        if nums[start] == target:
            return start
        else:
            return -1
    mid = (start+end)//2
    if nums[start] < nums[mid]:
        if nums[start] <= target < nums[mid]:
            # 맞는 순서
            return binarySearch(start, mid, nums, target)
        else:
            # 맞는 순서 우측
            return binarySearch(mid, end, nums, target)
    else:
        # 꼬인 순서
        if nums[mid] <= target <= nums[end-1]:
            # 우측 탐색
            return binarySearch(mid, end, nums, target)
        else:
            # 좌측 탐색
            return binarySearch(start, mid, nums, target)

결과