Gfg Mininum Number In A Sorted Rotated Array
Problem Statement
- Given an array of distinct elements which was initially sorted.Â
- This array is rotated at some unknown point.
- The task is to find the minimum element in the given sorted and rotated array.
Example
Input:
N = 5
arr[] = {3,4,5,1,2}
Output: 1
Explanation: The array is rotated
and the minimum element present is
at index (n-2) which is 1.
Solution Approaches
O(N) - Iterating from end
int minNumber(int arr[], int low, int high)
{
if (arr[high] > arr[low]) {
return arr[low];
}
else {
while (arr[high - 1] < arr[high]) {
high--;
}
return arr[high];
}
}
O(logN) - Binary Search
- Implementing basic binary search using given
low, high and mid
. - The smallest value in
...5-1-2...
is the mid value. - This follows that pattern in sorted rotated array that
arr[mid-1] > arr[mid]
and alsoarr[mid] < arr[mid+1]
. - But this above condition will give error if the smallest value is found at ends of array or size of array is <3.
- To overcome this we can make use of sorted-array property.
-
arr[high]>arr[low]
is true when there is no rotation at all. -
arr[high-1]>arr[high]
is true when there is unit rotation.
-
int minNumber(int arr[], int low, int high)
{
if (arr[high] > arr[low]) {
return arr[low];
}
else if (arr[high - 1] > arr[high]) {
return arr[high];
}
else {
int mid = (low + high) / 2;
while (!(arr[mid - 1] > arr[mid] and arr[mid] < arr[mid + 1])) {
mid = (low + high) / 2;
if (arr[mid] > arr[high]) {low = mid;}
else {high = mid;}
}
return arr[mid];
}
}
Return to DSA