Home » Technical Interview Questions » Array Interview Questions » Find the minimum element in a sorted and rotated array

# Find the minimum element in a sorted and rotated array

Given a sorted array which is rotated at some unknown point, find the minimum element in that array

### Example

INPUT :
arr[] = {5,6,7,1,2,3,4}

OUTPUT :
The minimum element is 1

In the above example, the input is the rotated sorted array ie, sorted array will be {1,2,3,4,5,6,7} and  the rotated sorted array is {5,6,7,1,2,3,4}. The output 1 is the minimum element in that array.

Time Complexity: O(logn)

The main idea is, the element is said to be minimum in rotated sorted array if the previous element to it is greater than it or there is no previous element(ie, no rotation)
We can do this using Binary search

## Algorithm

1. Find the mid element ie, mid = (low+high)/2

2. If the (mid+1)th element is less than mid element then return (mid+1)th element

3. If the mid element is less than (mid-1)th element then return the mis element

4. If the last element is greater than mid element then search in left half

5. If the last element is less than mid element then search in right half

## C++ Program

```#include <bits/stdc++.h>
using namespace std;
int findMinimum(int arr[],int low, int high)
{
int mid = (low + high)/2;
//when array is not rotated at all
if (arr[high] > arr[low])
{
return arr;
}
//if there is only one element
if (high == low)
{
return arr[low];
}
//if the element (mid + 1) is the minimum
if (mid< high && arr[mid+1] <arr[mid])
{
return arr[mid+1];
}
//If the mid element is the minimum
if (mid > low && arr[mid] <arr[mid-1])
{
return arr[mid];
}
//search in the left half
if (arr[high]>arr[mid])
{
return findMinimum(arr, low, mid-1);
}
//search in the right half
else
{
return findMinimum(arr,mid+1,high);
}

}
int main()
{
int arr[]= {5,6,7,1,2,3,4};  //creating an array
int n = sizeof(arr)/sizeof(arr); //size of the array
cout<<"The minimum element is "<<findMinimum(arr,0,n-1);
return 0;
}```

## Given a sorted array which is rotated at some unknown point, find the minimum element in that array

### Example

INPUT :
arr[] = {5,6,7,1,2,3,4}

READ  Count Pairs Whose Products Exist in Array

OUTPUT :
The minimum element is 1

In the above example, the input is the rotated sorted array ie, sorted array will be {1,2,3,4,5,6,7} and  the rotated sorted array is {5,6,7,1,2,3,4}. The output 1 is the minimum element in that array.

Time Complexity: O(logn)

The main idea is, the element is said to be minimum in rotated sorted array if the previous element to it is greater than it or there is no previous element(ie, no rotation)
We can do this using Binary search

## Algorithm

1. Find the mid element ie, mid = (low+high)/2

2. If the (mid+1)th element is less than mid element then return (mid+1)th element

3. If the mid element is less than (mid-1)th element then return the mis element

4. If the last element is greater than mid element then search in left half

5. If the last element is less than mid element then search in right half

## C++ Program

```#include <bits/stdc++.h>
using namespace std;
int findMinimum(int arr[],int low, int high)
{
int mid = (low + high)/2;
//when array is not rotated at all
if (arr[high] > arr[low])
{
return arr;
}
//if there is only one element
if (high == low)
{
return arr[low];
}
//if the element (mid + 1) is the minimum
if (mid< high && arr[mid+1] <arr[mid])
{
return arr[mid+1];
}
//If the mid element is the minimum
if (mid > low && arr[mid] <arr[mid-1])
{
return arr[mid];
}
//search in the left half
if (arr[high]>arr[mid])
{
return findMinimum(arr, low, mid-1);
}
//search in the right half
else
{
return findMinimum(arr,mid+1,high);
}

}
int main()
{
int arr[]= {5,6,7,1,2,3,4};  //creating an array
int n = sizeof(arr)/sizeof(arr); //size of the array
cout<<"The minimum element is "<<findMinimum(arr,0,n-1);
return 0;
}```
 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions