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.