Minimum element in rotated sorted array

Minimum element in rotated sorted array

Given a sorted array of integers, which is rotated by K positions, find minimum number in that array. This problem is commonly known as find minimum element in rotated sorted array.

What does rotation of array means?
Rotation here means last element of array, a[end] becomes first, a[0] and first element is moved to second a[1], second a[1] to third a[2] and second last element a[end-1] to last position a[end]. This is repeated for K times if array is rotated by K positions. Below array is rotated by 4 positions.

minimum element in sorted rotated arrayminimum element in rotated sorted array example

Now that we know what is rotated array, let’s see some examples for problem asked.

Original array : A = [1,2,3,4,5]
Rotated array : A = [4,5,1,2,3] By 2 positions.
Minimum element in array is 1.

A = [7,8,10,4,6] A is rotated by 3 positions. Minimum element is 4.

Questions to be asked to interviewer: whether negative numbers are allowed? Whether duplicates are allowed?

Methods to find minimum element in rotated sorted array

Brute force

Scan through entire array and check if a[i+1] is less than a[i], then a[i+1] is minimum element. If there is no such element in array, then a[0] is minimum element. This method works well with negative and duplicate numbers.

Complexity of brute force method to find minimum element in sorted rotate array is O(n).

Binary search
In problem statement, we have been told than array was initially sorted. That should ring bells. If a sorted array can be used to apply binary search, why not a sorted rotated array?

Binary search algorithm is used whenever the input space is sorted and some element is to be searched. At every step of algorithm, some part of input space is discarded. In binary search algorithm, input space is reduced to half in every iteration. Added constraint is in this problem is that sorted array is also rotated.

Idea here is that all the elements on right side of minimum element will be greater than it.

We randomly pick any index i and check if all elements on the right side are greater. We don’t need to go through every element, compare it with the last element a[end], if a[end]>a[i],  then the pivot is definitely not between index i and end. (Remember we are working sorted array). Discard entire array right side of the array and look for element in left part of the array. If a[end] <a[i] then look for element in right part of the array.  With above method, part of input space is reduced and if take index i as mid of array, then input space is reduced by half. Figure explains these conditions.

minimum element in rotated sorted array using binary search

Now what is the condition which is peculiar to the minimum or pivot element in array. By looking at examples above, it is clear that if i is the minimum element than a[i]<a[i-1].

So, if mid of array is taken we need to just check if a[mid] < a[mid-1]. We can avoid another call to input space by comparing a[mid+1] with a[mid]. In that case, if a[mid+1] < a[mid] then return a[mid+1].

Minimum element in rotated sorted array : recursive implementation

#include <stdio.h>
 
int findMinimum(int a[], int start, int end){
 
    int mid = start + (end-start)/2;
 
    if(start == end) return mid;
 
    if (start > end) return 0;
 
    /* This is condition for pivot element */
    if(mid > start && a[mid] < a[mid-1])
      return mid;
 
    if(mid < end && a[mid] > a[mid+1])
      return mid+1;

    /* If right side array is sorted then look in left sub array */
    else if(a[mid] < a[end])
      return findMinimum(a, start, mid);

    /* else look in right sub array */
    else
      return findMinimum(a, mid+1, end);
}
 
int main(void) {
 
	int a[] = {1,2,3,4};
	int size = sizeof(a)/sizeof(a[0]);
 
	int minElement = findMinimum(a,0,size-1);
	printf("Minimum element : %d", a[minElement]);
 
	return 0;
}

Iterative implementation

#include<stdio.h>
#include<stdlib.h>
 
int findMinimum(int array[], int low, int high){
 
    /* 
      Always restrict the search to the unsorted 
      sub-array. The min is always there.
    */
    while (array[low] > array[high]) {

        // find mid of array.
        int mid = (low + high)/2;

        // decide which sub-array to continue with.
        if (array[mid] > array[high]) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return array[low];
}
 
int main(){
 
	int a[] = {2,3,4,1};
	int size = sizeof(a)/sizeof(a[0]);
 
	printf("\n Minimum element : %d", findMinimum(a,0, size-1));
	return 0;
}

Complexity of binary search method to find minimum element in rotated sorted array is O(log N).

Test cases

Test case 1 :  Empty array is sent
Test case 2 :  No rotation in array. A = [1,2,3,4,5]
Test case 3 :  Completely rotated array A = [2,3,4,5,1]
Test case 4 :  Normally rotated array A = [3,4,1,2]

Please share your suggestions in comments. Contact us in case you want to contribute to this blog, guest posts are most welcome!