# Find Minimum In Rotated Sorted Array

Difficulty Level Easy
Frequently asked in Adobe Amazon Microsoft Morgan Stanley Samsung Snapdeal Times Internet
Array Binary Search Divide and Conquer SearchingViews 1794

## Problem Statement

“Find Minimum In Rotated Sorted Array” states that you are given a sorted array of size n which is rotated at some index. Find the minimum element in the array.

## Example

`a[ ] = {5, 1, 2, 3, 4}`
`1`

Explanation: If we arrange the array in sorted order it will be [1, 2, 3, 4, 5]. So the smallest number out of all these is 1. And that’s why the output is 1.

`a[ ] = {5, 2, 3, 4}`
`2`

## Linear Search

### Algorithm

```1. Initialize a sorted rotated array a[ ] of size n.
2. Create a function to find the minimum in a rotated sorted array which accepts an integer variable as it's a parameter.
3. Initialize an integer variable min as the first element in the given array.
4. Traverse through the given array and check if the element at current index in array a[ ] is less than variable min, update min as current element.
5. Return the integer variable min.```

We can use linear search or simply traverse the input array once and find the smallest element in a single traversal. We will simply loop over all the elements in the array and if we find a number which is lesser than our minimum, then we update our answer.

### Code

#### C++ Program to find minimum in rotated sorted array

```#include <bits/stdc++.h>
using namespace std;

int findMin(int a[], int n){
int min = a[0];
for(int i=1; i<n; i++){
if(a[i]<min){
min = a[i];
}
}
return min;
}

int main() {
int a[] = {5, 2, 3, 4};
int n = sizeof(a)/sizeof(a[0]);
cout<<findMin(a, n);
return 0;
}
```
`2`

#### Java Program to find minimum in rotated sorted array

```class MinSearch{

static int findMin(int a[], int n){
int min = a[0];
for(int i=1; i<n; i++){
if(a[i]<min){
min = a[i];
}
}
return min;
}

public static void main (String[] args){
int a[] = {5, 2, 3, 4};
int n = a.length;
System.out.println(findMin(a, n));
}
}

```
`2`

### Complexity Analysis

#### Time Complexity

O(N),  because we traversed over all the elements in the array, which has allowed us to achieve a linear time complexity.

#### Space Complexity

O(1), the algorithm itself takes constant space but the program as a whole takes linear space because of storing the input array.

## Binary Search

### Algorithm

```1. Initialize a sorted rotated array a[ ] of size n.
2. Create a function to find the minimum in a rotated sorted array which accepts an integer variable as it's a parameter.
3. Initialise the three variables beg = 0, end = n-1 and mid = beg+(end-beg)/2.
4. Check if the variable end is less than the variable beg, return a[0].
5. If the variable end is equal to the variable beg, return a[beg].
6. If the variable mid is less than the variable end and a[mid+1] is less than a[mid], return a[mid+1].
7. If mid is greater than beg and a[mid] is less than a[mid+1], return a[mid].
8. If a[end] is greater than a[mid], make a recursive call to function with parameters a, beg, mid-1.
9. Return the recursive call to function itself with the parameters a, mid+1, and end.```

The more efficient approach will be to use binary search because the input array is a rotated sorted array. That is the array is sorted but it was rotated at a single point. Since Binary search takes logarithmic time complexity. It’s better to use this solution as compared to the above one.

### Code to find minimum in rotated sorted array using binary search

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

int findMin(int a[], int beg, int end){
if(end < beg)
return a[0];

if(end==beg)
return a[beg];

int mid = beg + (end - beg)/2;

if(mid<end && a[mid + 1]<a[mid])
return a[mid + 1];

if(mid>beg && a[mid]<a[mid - 1])
return a[mid];

if(a[end]>a[mid])
return findMin(a, beg, mid - 1);
return findMin(a, mid + 1, end);
}

int main(){
int a[] = {5, 2, 3, 4};
int n = sizeof(a)/sizeof(a[0]);
cout<<findMin(a, 0, n-1);
return 0;
}```
`2`

#### Java Program

```class MinSearch{

static int findMin(int a[], int beg, int end){

if(end < beg)
return a[0];

if(end==beg)
return a[beg];

int mid = beg + (end - beg)/2;

if(mid<end && a[mid + 1]<a[mid])
return a[mid + 1];

if(mid>beg && a[mid]<a[mid - 1])
return a[mid];

if(a[end]>a[mid])
return findMin(a, beg, mid - 1);
return findMin(a, mid + 1, end);
}

public static void main (String[] args){
int a[] = {5, 2, 3, 4};
int n = a.length;
System.out.println(findMin(a, 0, n-1));
}
}```
`2`

### Complexity Analysis

#### Time Complexity

O(log N) where N is the number of elements in the input array. Here we used binary search which takes logarithmic time complexity. All of this possible because the array was initially sorted.

#### Space Complexity

O(1), this approach takes also constant time but the program as a whole takes O(N) space because of the space required to store the input.

Translate »