Home » Data Structure » Array Data Structure

Find the minimum element in a sorted and rotated array

C++ implementation to find the minimum element in a sorted and rotated array using multiple approaches.
Submitted by Vikneshwar GK, on February 26, 2022

Consider a sorted integer array, of size n, that has distinct elements and sorted at some unknown points. The task at hand is to find the minimum element in this array.

Example:

Input:
array[]= {4, 5, 1, 2, 3}
            
Output:
Minimum element: 1

Input:
array[]= {60, 70, 30, 40, 50}
	
Output:
Minimum element: 30

Solution 1: Using Binary Search

This is a simple yet efficient approach to find the minimum element in a sorted and rotated array. On observing the array, we can notice that the minimum element is the one that has a previous element greater than itself, i.e., array[i-1]>array[i]. If there is no element like this, then the first element is the minimum element. 

• Find the mid value of the array and compare it with mid-1 and mid+1
• If mid element is lesser than the last element, then the minimum element lies in the first half
• If mid element is greater than the last element, then the minimum element lies in the other half

C++ Implementation:

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

// Function to find the minimum value
// in sorted and rotated array
int findMin(int array[], int low, int high)
{
    // if array is not rotated
    if (high < low)
        return array[0];

    // if array contains only one element
    if (high == low)
        return array[low];

    // Find mid
    int mid = low + (high - low) / 2;

    // check if minimum element is present at
    // mid+1 and mid-1
    if (mid < high && array[mid + 1] < array[mid])
        return array[mid + 1];

    if (mid > low && array[mid] < array[mid - 1])
        return array[mid];

    // if minimum present in the left half
    if (array[high] > array[mid])
        return findMin(array, low, mid - 1);
    // if minimum present in the right half
    return findMin(array, mid + 1, high);
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    cout << "Minimum element: " << findMin(array, 0, N - 1);

    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 4
Enter element 2: 5
Enter element 3: 6
Enter element 4: 1
Enter element 5: 2
Minimum element: 1

Time Complexity: O(log(n)), where n is the length of the array.

Special Case - Handling duplicate elements

This is a space efficient approach that will not use a temporary array to perform the rotation for multiple k values.

C++ Implementation:

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

// Function to find the minimum value
// in sorted and rotated array
int findMin(int array[], int low, int high)
{
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (array[mid] == array[high])
            high--;
        else if (array[mid] > array[high])
            low = mid + 1;
        else
            high = mid;
    }
    return array[high];
}

// Main function
int main()
{
    int array[100], N, element;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    cout << "Minimum element: " << findMin(array, 0, N - 1);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1: 4
Enter element 2: 5
Enter element 3: 5
Enter element 4: 1
Enter element 5: 2
Enter element 6: 3
Minimum element: 1

Time Complexity: O(log(n)), where n is the length of the array.