[LeetCode] 33. Search in Rotated Sorted Array

Problem

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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -10^4 <= target <= 10^4

Solution

Approach

1. 리스트에 추가되는 문자열을 만들어 나갈 때, 여는 괄호의 개수는 n의 절반을 넘기면 안되고, 닫는 괄호는 현재까지 만들어진 문자열에서 여는 괄호의 개수보다 많으면 안된다.

Algorithm

Complexity Analysis

• Time Complexity

본 알고리즘은 이진 탐색을 수행하기 때문에 배열 nums의 길이(n)에 따라 while반복문(6)의 반복횟수는 모든 경우에 logn이 된다. 따라서 O(logn)의 시간 복잡도를 가진다.

• Space Complexity

배열 nums의 길이(n)에 따라 감소하거나 증가되어 할당받는 공간이 없으므로 O(1)의 공간 복잡도를 가진다.