Home » Interview coding problems/challenges

Find Minimum in Rotated Sorted Array

Here, we are going to find the solution to find the minimum in rotated sorted array with C++ implementation.
Submitted by Divyansh Jaipuriyar, on August 27, 2020

Problem statement

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element. You may assume no duplicate exists in the array.

Problem description:

The given problem wants you to use the concept that the array is already sorted but at some point, the array is rotated and you are required to use the concept of binary search such that instead of traversing you complete the searching operation in logarithmic time.

Note: This problem is sometimes also asked in a different way, where we have to count the number of times the sorted array is rotated either in clockwise or counterclockwise. In this question, we just need to return the index of the minimum element.

Input

The first line of the input consists of T number of test cases, each test case consists of N size of array, and the following line consists of N number of elements.

Output

You need to print the minimum value of the element.

Examples

Input:
T=1
N=7
[4,5,6,7,0,1,2]

Output:
0

0 is the minimum value in the given array.

Input:
T=1
N=5
[3,4,5,1,2]

Output:
1
1 is the minimum value in the given array.

Solution Approach

(a) Brute Force Approach:

In this approach, we will simply traverse from the first element of the array to the last element of the array until we get the minimum element from the array.

Following steps will be involved:

• Step 1: Initialise some variable ans with maximum value.
• Step 2: Now traverse from first to the last element and compare ans with array element, update the minimum value to ans.
• Step 3: Print the ans.

Time complexity for the brute force approach in the worst case is O(n)

Space complexity for the brute force approach in the worst case is O(1)

C++ Implementation

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

typedef long long ll;

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;

        cout << "Enter elements: ";
        ll arr[n];
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        //declare temporary variable.
        ll ans = INT_MAX;
        //iterativily find minimum element.
        for (ll i = 0; i < n; i++)
            ans = min(ans, arr[i]); //assign minimum value,
        cout << ans << "\n";
    }
    
    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 6
Enter elements: 6 5 4 1 2 3
1
Enter size of array: 5
Enter elements: 3 4 5 1 2
1
Enter size of array: 7
Enter elements: 4 5 6 7 0 1 2
0

(b) Binary Search Approach:

In this method, we will use a binary search. If you carefully observe then we can find that the minimum element lies in the unsorted half of the array. So we need to perform binary search operation in unsorted half.

We will perform the following operation:

• Step 1: First we will compare the last element with the first element of the array is already sorted then we don't need to compare further, simply return the first element.
• Step 2: If the above case fails then we need to find the mid element, if the mid element is smaller than its left side element and right side element then will return the mid element as it is the minimum element.
• Step 3: If the above case fails then we need to check in which half the minimum element lies, we will compare the first and mid element if the mid element is greater than the first element then it means element before the mid element is sorted so will search in the right side of the array.
• Step 4: if the above case fails then we will make a search in the left side of the mid element.
• Step 5: we will keep searching until left>right.

Time complexity of the above approach in the worst case is O(log(n))

Space complexity of above approach in the worst case is O(1)

C++ Implementation

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

typedef long long ll;

//declare solve function.
ll solve(ll arr[], ll n, ll st, ll en)
{
    //initialize left index.
    ll l = st;

    //initialize right index.
    ll r = en - 1;

    //perform binary search.
    while (l < r) {
        //find mid index.
        ll mid = l + (r - l) / 2;

        //if array is already sorted.
        if (arr[l] < arr[r])
            return arr[l];

        //if right half is unsorted
        if (arr[mid] >= arr[l])
            l = mid + 1;
        else
            r = mid;
    }
    return arr[l];
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of array: ";
        ll n;
        cin >> n;

        cout << "Enter elements: ";
        ll arr[n];
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
        cout << solve(arr, n, 0, n) << "\n";
    }

    return 0;
}

Output

Enter number of test cases: 3
Enter size of array: 6
Enter elements:4 5 6 0 1 2 
0
Enter size of array: 5
Enter elements: 3 4 5 1 2
1
Enter size of array: 7
Enter elements: 4 5 6 7 0 1 2
0