Problem: Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
- [4,5,6,7,0,1,2] if it was rotated 4 times.
- [0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
Example:
Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
Approach: We are going to use binary search. While comparing the mid element, we would have these three conditions -
- arr[mid - 1] > arr [mid] < arr[mid + 1]. Got the minimum just return arr[mid]. We need to take care of boundary conditions here.
- arr[mid] > arr[high]. That's the only condition where the min element is on the right side. It happened because of rotation.
- Otherwise the min element is on left side.
Implementation in C#:
Using Recursion:
public int FindMinInRotatedArray(int[] nums)
{
if (nums?.Length == 0)
{
return -1;
}
return this.FindMinInRotatedArray(nums, 0, nums.Length - 1);
}
private int FindMinInRotatedArray(int[] nums, int low, int high)
{
if (low == high)
{
return nums[low];
}
int mid = (low + high) / 2;
if ((mid == nums.Length - 1 || nums[mid] < nums[mid + 1]) &&
(mid == 0 || nums[mid] < nums[mid - 1]))
{
return nums[mid];
}
if (nums[mid] > nums[high]) // Go to right side
{
return FindMinInRotatedArray(nums, mid + 1, high);
}
else // Go to left side otherwise
{
return FindMinInRotatedArray(nums, low, mid - 1);
}
}
Without recursion:
public int FindMinInRotatedArray(int[] nums)
{
if (nums?.Length == 0)
{
return -1;
}
int low = 0, high = nums.Length - 1;
while(low < high)
{
int mid = (low + high) / 2;
if (nums[mid] > nums[high])
{
low = mid + 1;
}
else
{
high = mid;
}
}
return nums[high];
}
Complexity: O(logn)
No comments:
Post a Comment