[C++] LeetCode : Search in Rotated Sorted Array

Question

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.

---

 

오름차순으로 정렬된 정수 배열 nums가 있습니다. 배열은 모두 고유한 값 입니다. 

함수에 전달되기 전에,
nums는 결과 배열이 [nums[k], nums[k+1], ..., nums[n-1]이 되도록 알 수 없는 피벗 인덱스 k(1 <= k < nums.length)에서 회전할 수 있습니다. nums[0], nums[1], ..., nums[k-1]](0-인덱스).
 

 예를 들어, [0,1,2,4,5,6,7]은 피벗 인덱스 3에서 회전되어 [4,5,6,7,0,1,2]가 될 수 있습니다.

가능한 회전 후 배열 nums와 정수 대상이 주어지면 대상 인덱스가 nums이면 대상의 인덱스를 반환하고 nums가 아니면 -1을 반환합니다.

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

 

제약사항

• 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

---

Solution1 (Bruth Force)

단순하다 순차 탐색으로 target이 있는지 확인한다.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(int i=0; i<nums.size(); i++){
			if(nums[i] == target) return i;
		}
		return -1;
    }
};

• Time Complexity : O(n)
• Space Complexity : O(1)

Solution2

숫자를 다 봐야 할까? 오름차순 배열이 rotated 한 배열이 주어졌다면, 어떤 값 k를 기준으로 좌, 우 가 각각 오름차순 배열을 만족한다는 뜻이다. 
즉, nums[k] > nums[k+1] 인 k를 찾고, 그것을 기준으로, 다시 왼쪽 오른쪽 탐색을 해준다면 
O(logN) + O(logk) + O(log(N-K) = O(logN) 을 만족한다.

class Solution {
public:
	int binary_search(vector<int> &nums, int start, int end){
		if(start == end) return 0;
		int mid = (start + end) / 2;
		
		if(nums[mid] > nums[mid+1]) return mid;
		
		return binary_search(nums, start, mid)+binary_search(nums, mid+1, end);
	}
	int binary_search2(vector<int> &nums, int start, int end, int target){
		if(start == end) {
			if(nums[start] == target) return start;
			return -1;
		}
		int mid = (start + end) / 2;
		
		if(nums[mid] == target) return mid;
		else if(nums[mid] < target) return binary_search2(nums, mid+1, end, target);
		else{
			return binary_search2(nums, start, mid, target);
		}
	}
	
	int search(vector<int>& nums, int target) {
		int n = nums.size();
		if(n == 1) return (nums[0] == target) ? 0 : -1;
		
		int k = binary_search(nums, 0, n-1);
		
		int ans = -1;
		ans = binary_search2(nums, 0, k, target);
		if(ans == -1) ans = binary_search2(nums, k+1, n-1, target);
		
		return ans;
    }
};

• Time complexity : O(logN) 
• Space Complexity : O(logN) 

 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/804/

Explore - LeetCode