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[0];
	}
	//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[0]); //size of the array
    cout<<"The minimum element is "<<findMinimum(arr,0,n-1);
    return 0;
}
Try It


Next > < Prev
Scroll to Top