Find the Minimum element in a Sorted and Rotated Array

Given a sorted rotated array, the task is to find index of minimum element of the array. Following solution assumes that all elements are distinct.

Examples:

Input : arr[] = {5, 6, 1, 2, 3, 4}
Output : 2
Minimum element in the array is 1, hence index will be 2

Input : arr[] = {2, 3, 4, 5, 6, 7, 8, 1}
Output : 7
Minimum element in the array is 1, hence index will be 7

A Simple Approach is to traverse the complete array and find the index of minimum element. This solution requires O(N) time.

C++

// C++ program to find index of minimum 
// element in a sorted rotated array
#include <bits/stdc++.h>
using namespace std;

int PivotInSortedRotated(int arr[], int size)
{
    int piv = -1;
    if (arr != NULL && size > 0)
    {
        piv = 0;
        for (int i = 0; i < size - 1; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                piv = i + 1;
                break;
            }
        }
    }
    
    return piv;
}

// Driver code
int main()
{
    // Sorted Rotated Array
    int arr[] = {5, 6, 1, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Index of minimum element in the array: " << PivotInSortedRotated(arr, n) << endl;
    
    return 0;
}

Java

// Java program to find index of minimum 
// element in a sorted rotated array
import java.util.*;

class GFG
{
    public static int PivotInSortedRotated(int arr[], int size)
    {
        int piv = -1;
        if(arr != null && size > 0)
        {
            piv = 0;
            for(int i = 0; i < size-1; i++)
            {
                if(arr[i] > arr[i + 1])
                {
                    piv = i + 1;
                    break;
                }
            }
        }
        return piv;
    }
    
    // Driver code    
    public static void main (String[] args) 
    {
        // Sorted Rotated Array
        int arr[] = {5, 6, 1, 2, 3, 4};
        int len = arr.length;
        
        System.out.println("Index of minimum element in an array: " + 
                          PivotInSortedRotated(arr, len));
    }
}

Output :

Index of minimum element in an array: 2

A Better Approach is to use Binary Search which takes O(Log(N)) time. If we look at the pattern of the above examples.

If arr[0] <= arr[size – 1], then array is not rotated at all and the index would be definitely 0.
If the array is rotated then we will check for arr[mid + 1] element is minimum or not by comparing with arr[mid]. if so then (mid + 1) will be the answer.
If arr[low] <= arr[high], then it means that elements from low to middle are all in sorted order. Then we will do search in the second half i.e low = mid + 1. Else we search in the first half i.e. high = mid – 1.

Below is the implementation of above approach:

C++

// C++ program to find the index of the minimum element in a sorted rotated array
#include <iostream>
using namespace std;

int PivotInSortedRotated(int arr[], int low, int high)
{
    if (arr == NULL || high < low)
        return -1;

    // When the array is not rotated, the first index is pivoted
    if (high == low || arr[low] < arr[high])
        return low;

    while (low <= high)
    {
        int mid = (low + high) / 2;
        int next = (mid + 1) % (high + 1);
        int prev = (mid + high) % (high + 1);

        // If mid is the pivot
        if (arr[mid] < arr[next] && arr[mid] < arr[prev])
            return mid;

        // If the right half is sorted, the pivot is in the left half
        if (arr[mid] < arr[high])
            high = mid - 1;

        // If the left half is sorted, the pivot is in the right half
        else if (arr[mid] >= arr[low])
            low = mid + 1;
    }

    return -1;
}

// Driver code
int main()
{
    int arr[] = {5, 6, 1, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    int pivotIndex = PivotInSortedRotated(arr, 0, n - 1);

    if (pivotIndex != -1)
        cout << "Index of the minimum element in the array: " << pivotIndex << endl;
    else
        cout << "Array is not rotated." << endl;

    return 0;
}

Java

// Java program to find the index of the minimum element in a sorted rotated array
import java.util.*;

class GFG
{
    public static int PivotInSortedRotated(int arr[], int low, int high)
    {
        if (arr == null || high + 1 == 0)
            return -1;

        // When the array is not rotated, the first index is pivoted
        if (high + 1 == 0 || arr[0] < arr[high])
            return 0;

        int len = high;
        while (low <= high)
        {
            int mid = (low + high) / 2;

            // If mid + 1 is the pivot or not
            if (mid < len && arr[mid] > arr[mid + 1])
                return mid + 1;

            else if (arr[low] <= arr[mid])
                // If arr[low] <= arr[mid], it means from low to mid, all elements are in sorted order,
                // so the pivot will be in the second half
                low = mid + 1;
            else
                // Otherwise, the pivot lies in the first half, so we find the pivot in the first half
                high = mid - 1;
        }
        return -1;
    }

    // Driver code
    public static void main(String[] args)
    {
        // Sorted Rotated Array
        int arr[] = {5, 6, 1, 2, 3, 4};
        int len = arr.length;

        int pivotIndex = PivotInSortedRotated(arr, 0, len - 1);

        if (pivotIndex != -1)
            System.out.println("Index of the minimum element in the array: " + pivotIndex);
        else
            System.out.println("Array is not rotated.");
    }
}

Output :

Index of minimum element in an array: 2