[LeetCode] Search in Rotated Sorted Array
Search in Rotated Sorted Array
Category: Array
Deadline: 1st week (12/31 - 1/7)
Difficulty: Medium
LeetCode link: https://leetcode.com/problems/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
public class Solution
{
public int Search(int[] nums, int target)
{
int idx = -1;
Find(nums, 0, nums.Length - 1, ref idx, target);
return idx;
}
public void Find(int[] nums, int start, int end, ref int ans, int target)
{
if (end - start < 2)
{
if (nums[start] == target)
{
ans = start;
}
else if (nums[end] == target)
{
ans = end;
}
}
else
{
int pivot = (int)(end + start) / 2;
if (nums[pivot] < nums[end])
{
// case a
if (nums[pivot + 1] <= target && nums[end] >= target)
{
Sorted(nums, pivot + 1, end, ref ans, target);
}
else
{
Find(nums, start, pivot, ref ans, target);
}
}
else if (nums[pivot] > nums[end])
{
// case b
if (nums[start] <= target && nums[pivot] >= target)
{
Sorted(nums, start, pivot, ref ans, target);
}
else
{
Find(nums, pivot + 1, end, ref ans, target);
}
}
}
}
public void Sorted(int[] nums, int start, int end, ref int ans, int target)
{
if (end - start < 2)
{
if (nums[start] == target)
{
ans = start;
}
else if (nums[end] == target)
{
ans = end;
}
}
else
{
int pivot = (int)(end + start) / 2;
if (nums[pivot] == target)
{
ans = pivot;
}
else if (nums[pivot] > target)
{
Sorted(nums, start, pivot, ref ans, target);
}
else
{
Sorted(nums, pivot + 1, end, ref ans, target);
}
}
}
}
Comment
- Find Minimum in Rotated Sorted Array의 알고리즘과 유사함. 단, 앞선 문제는 crack을 찾는 것이 관건이었다면, 이번 문제는 target이 어디에 속하는지를 찾는 것이 중요하므로, crack이 없는 부분(즉, 연속된 수열임이 보장된 Subarray)의 범위 내에 target이 속하는지를 한번 더 물어볼 것이다. -> 이진 검색에서 다음과 같은 4가지 상황이 발생할 수 있다.
- crack이 pivot 우측에 존재한다 (nums[pivot] > nums[end]) -> 좌측 Subarray는 연속성이 보장되었으므로, 다시한번 조사, -> target이 nums[strt]와 nums[pivot] 사이에 존재한다(nums[strt] < target < nums[pivot]) -> 좌측 Subarray를 조사하면됨! (단, 이미 정렬이 보장되었으므로 더 간단한 이진검색 함수인 Sorted를 사용하자)
- crack이 pivot 우측에 존재한다(nums[pivot] > nums[end]) -> 하지만 target이 nums[strt]와 nums[pivot] 사이에 존재하지 않는다 -> 우측 Subarray를 재귀적으로 조사하면됨! -> Find(strt,pivot)
- crack이 pivot 좌측에 존재한다 + (nums[pivot] < target < nums[end])를 만족한다 -> Sorted(pivot,end)
- crack이 pivot 좌측에 존재한다 + 위 조건을 만족하지 않는다 -> 우측 array를 재귀적으로 탐색 -> Find(pivot+1, end)
- Find(배열, 시작점, 끝점, 현재 pointer 위치) : 이진 검색, O(logn)으로 검색하기 위해 만들어진 재귀함수. Find Minimum in Rotated Sorted Array의 Find 함수와 동일.
- Sorted : 이미 오름차순으로 정렬된 수열에 대해서는 훨씬 간단한 이진검색이 적용가능.
- 그렇게 해서 얻어진 값이 target과 다르다면 -1을 출력 (문제 조건).