Problem: It is same as previous Find Minimum in Rotated Sorted Array but here the array contains duplicates.
Approach: We just need one additional check to make it work in this case which is - if arr[mid] is equals to arr[high] then we just reduce high by 1.
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]) // Additional check
{
--high;
}
else if (nums[mid] > nums[high])
{
low = mid + 1;
}
else
{
high = mid;
}
}
return nums[high];
}
No comments:
Post a Comment