Find the Minimum Element in a Sorted and Rotated Array

Difficulty Level Medium
Frequently asked in Amazon Bloomberg Facebook Goldman Sachs Microsoft Oracle
Array Binary SearchViews 2890

Problem Statement

In the “Find the Minimum Element in a Sorted and Rotated Array” problem we have given a sorted array a[]. This array is rotated at some unknown point, find the minimum element in this array.

Input Format

The first and only one line containing an integer value n.

Second-line containing n space-separated integer.

Output Format

The first and only one line containing an integer value x denoting the minimum element in the given array.

Constraints

  • 1<=n<=10^6
  • 1<=a[i]<=a[i+1]<=10^9

Example

4
5 6 1 2
1

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

Algorithm

The main idea is, the element is said to be minimum in the 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-

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

Implementation

C++ Program to Find the Minimum Element in a Sorted and Rotated Array

#include <bits/stdc++.h> 
using namespace std; 
    
int main() 
{ 
    int n;
    cin>>n;
    vector<int> v;
    for(int j=0;j<n;j++)
    {
        int p;
        cin>>p;
        v.push_back(p);
    }
    int l = 0;
    int r = n-1;
    int last = v[r];
    while(l<r) 
    {
        int mid=l+(r-l)/2;
        if(v[mid]>last) 
        {
            l=mid+1;
        } 
        else 
        {
            r=mid;
        }
    }
    cout<<v[l]<<endl;
  return 0; 
}

Java Program to Find the Minimum Element in a Sorted and Rotated Array

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        int v[] = new int[n];
        for(int i=0;i<n;i++)
        {
            v[i]=sr.nextInt();
        }
        int l = 0;
        int r = n-1;
        int last = v[r];
        while(l<r) 
        {
            int mid=l+(r-l)/2;
            if(v[mid]>last) 
            {
                l=mid+1;
            } 
            else 
            {
                r=mid;
            }
        }
        System.out.println(v[l]);
    }
}

6
4 5 6 3 4 4
3

Complexity Analysis to Find the Minimum Element in a Sorted and Rotated Array

Time Complexity

O(logn) where n is the size of the given array. Here we use binary search algorithm which leads us to logn time complexity.

Space Complexity

O(1) because we don’t create any auxiliary space here.

Translate »