33. Search in Rotated Sorted Array - 1주차 알고리즘 코딩 인터뷰 공부

33. Search in Rotated Sorted Array

오름차순으로 정수 array, nums가 있습니다. (Element 들이 연속된 정수는 아닐 수 있습니다)

Function 에 pass 되기 전에 nums 는 k(랜덤) 만큼 array 내에서 왼쪽으로 회전을 하게 됩니다.

Target 이 되는 element 의 index 를 return 하시오. Array 내에 target 이 없으면 -1 을 return 하시오.

알고리즘은 시간 복잡도: O(log n) 가 되게 하시오.

 

예시1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

예시2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

예시3:

Input: nums = [1], target = 0
Output: -1

 

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

 

.

.

.

.

.

.

풀이

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

    if nums[l] <= nums[mid]:
        if nums[l] <= target <= nums[mid]:
            r = mid -1
        else:
            l = mid + 1
    else:
        if nums[mid] <= target <= nums[r]:
            l = mid + 1
        else:
            r = mid - 1
return -1

런타임: 37 ms, 65.02%

메모리 사용: 13.7 MB, 65.86%

 

시간복잡도: O(logn)

공간복잡도: O(1)