Open In App

Find the Minimum element in a Sorted and Rotated Array

Last Updated : 17 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given a sorted array arr[] (may be distinct or may contain duplicates) of size N that is rotated at some unknown point, the task is to find the minimum element in it. 

Examples: 

Input: arr[] = {5, 6, 1, 2, 3, 4}
Output: 1
Explanation: 1 is the minimum element present in the array.

Input: arr[] = {1, 2, 3, 4}
Output: 1

Input: arr[] = {2, 1}
Output: 1

Find the Minimum element in a Sorted and Rotated Array using Linear Search:

A simple solution is to use linear search to traverse the complete array and find a minimum. 

Follow the steps mentioned below to implement the idea:

  • Declare a variable (say min_ele) to store the minimum value and initialize it with arr[0].
  • Traverse the array from the start.
    • Update the minimum value (min_ele) if the current element is less than it.
  • Return the final value of min_ele as the required answer.

Below is the implementation of the above approach.

C++
// C++ code  to implement the approach

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

// Function to find the minimum value
int findMin(int arr[], int n)
{
    int min_ele = arr[0];

    // Traversing over array to
    // find minimum element
    for (int i = 0; i < n; i++) {
        if (arr[i] < min_ele) {
            min_ele = arr[i];
        }
    }

    return min_ele;
}

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

    // Function call
    cout << findMin(arr, N) << endl;
    return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;

class GFG {

  // Function to find the minimum value
  static int findMin(int arr[], int n)
  {
    int min_ele = arr[0];

    // Traversing over array to
    // find minimum element
    for (int i = 0; i < n; i++) {
      if (arr[i] < min_ele) {
        min_ele = arr[i];
      }
    }

    return min_ele;
  }

  public static void main (String[] args) {
    int arr[] = { 5, 6, 1, 2, 3, 4 };
    int N = arr.length;
    System.out.println(findMin(arr, N));
  }
}

// This code is contributed by aadityaburujwale.
Python3
# python3 code  to implement the approach

def findMin(arr, N):
    
    min_ele = arr[0];

    # Traversing over array to
    # find minimum element
    for i in range(N) :
        if arr[i] < min_ele :
            min_ele = arr[i]

    return min_ele;

# Driver program
arr = [5, 6, 1, 2, 3, 4]
N = len(arr)

print(findMin(arr,N))

# This code is contributed by aditya942003patil
C#
// C# code to implement above approach
using System;
 
class Minimum {
 
    static int findMin(int[] arr, int N)
    {
        int min_ele = arr[0];
        
        // Traversing over array to
        // find minimum element
        for (int i = 0; i < N; i++) {
            if (arr[i] < min_ele) {
                min_ele = arr[i];
            }
        }
        
        return min_ele;
    }
 
    // Driver Program
    public static void Main()
    {
        int[] arr = { 5, 6, 1, 2, 3, 4 };
        int N = arr.Length;
       
        Console.WriteLine(findMin(arr, N));
 
    }
}
 
// This code is contributed by aditya942003patil.
Javascript
// JS code to implement the approach

// Function to find the minimum value
function findMin(arr, n) {
    let min_ele = arr[0];

    // Traversing over array to
    // find minimum element
    for (let i = 0; i < n; i++) {
        if (arr[i] < min_ele) {
            min_ele = arr[i];
        }
    }

    return min_ele;
}

// Driver code
let arr = [5, 6, 1, 2, 3, 4];
let N = arr.length;

// Function call
console.log(findMin(arr, N));

// This code is contributed by adityamaharshi21.

Output
1


Time Complexity: O(N)
Auxiliary Space: O(1)

Find the Minimum element in a Sorted and Rotated Array using Binary Search: 

We start by checking if the array is not rotated. If it is not rotated, the minimum element is simply the first element of the array.

If the array is rotated, we use binary search to narrow down the search space. We compare the middle element with the left and right elements to determine which half of the array contains the minimum element.

However, we need to handle the case where the middle element is equal to the left and right elements. This indicates that the array is rotated and the minimum element could be either the middle element, the left element, or the right element.

To handle this case, we update the minimum element to the minimum of the current minimum and the middle element. We then increment the left pointer and decrement the right pointer to continue the search.

By repeatedly narrowing down the search space and handling duplicates, we can efficiently find the minimum element in a rotated sorted array.

Below is the implementation of the above approach:

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

int findMin(vector<int>& arr, int low, int high)
{
    // If the array is not rotated
    if (arr[low] < arr[high]) {
        return arr[low];
    }
    int ans = 1e9;
    // Binary search
    while (low <= high) {
        int mid = (low + high) / 2;
        // if left most element is equal with right most and
        // middle element then we can reduce the search
        // space only by increasing the lower limit and
        // decreasing the upper limit
        if (arr[mid] == arr[low]
            and arr[mid] == arr[high]) {
            ans = min(ans,arr[mid]);
            low++;
            high--;
        }
        // If the left half is sorted, the minimum element
        // must be in the right half
        else if (arr[mid] > arr[high]) {
            low = mid + 1;
        }

        // If the right half is sorted, the minimum element
        // must be in the left half
        else {
            ans = min(ans,arr[mid]);
            high = mid - 1;
        }
    }

    // If no minimum element is found, return -1
    return ans;
}

// Driver program to test above functions
int main()
{
    vector<int> arr = {5, 6, 1, 2, 3, 4};
    int N = arr.size();
    cout << "The minimum element is "
         << findMin(arr, 0, N - 1) << endl;
    return 0;
}
Java
import java.util.*;

public class Main {
    public static int findMin(List<Integer> arr, int low,
                              int high)
    {
        // If the array is not rotated
        if (arr.get(low) < arr.get(high)) {
            return arr.get(low);
        }
        int ans = 1000000000;
        // Binary search
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr.get(mid)== arr.get(low) && arr.get(mid) == arr.get(high)) {
                    ans = Math.min(ans,arr.get(mid));
                    low++;
                    high--;
            }
            // If the left half is sorted, the minimum
            // element must be in the right half
            else if (arr.get(mid) > arr.get(high)) {
                low = mid + 1;
            }

            // If the right half is sorted, the minimum
            // element must be in the left half
            else {
                ans = Math.min(ans,arr.get(mid));
                high = mid - 1;
            }
        }

        // If no minimum element is found, return -1
        return ans;
    }

    // Driver program to test above functions
    public static void main(String[] args)
    {
        List<Integer> arr = new ArrayList<>(
            Arrays.asList(5, 6, 1, 2, 3, 4));
        int N = arr.size();
        System.out.println("The minimum element is "
                           + findMin(arr, 0, N - 1));
    }
}
Python3
def findMin(arr, low, high):
    # If the array is not rotated 
    if arr[low] < arr[high]:
        return arr[low]
    
    ans = float('inf')
    # Binary search
    while low <= high:
        mid = (low + high) // 2
        # if left most element is equal with right most and
        # middle element then we can reduce the search
        # space only by increasing the lower limit and
        # decreasing the upper limit
        if arr[mid] == arr[low] and arr[mid] == arr[high]:
            ans = min(ans, arr[mid])
            low += 1
            high -= 1
        
        # If the left half is sorted, the minimum element
        # must be in the right half
        elif arr[mid] > arr[high]:
            low = mid + 1
        
        # If the right half is sorted, the minimum element
        # must be in the left half
        else:
            ans = min(ans, arr[mid])
            high = mid - 1
    
    # If no minimum element is found, return -1
    return ans

# Driver program to test above functions
if __name__ == '__main__':
    arr = [5, 6, 1, 2, 3, 4]
    N = len(arr)
    print("The minimum element is " + str(findMin(arr, 0, N - 1)))
    
# This code is modified by Susobhan Akhuli
C#
using System;
using System.Collections.Generic;

public class Program {
  public static int findMin(List<int> arr, int low, int high) {
    // If the array is not rotated
    if (arr[low] < arr[high]) {
      return arr[low];
    }
    
    int ans = Int32.MaxValue;

    // Binary search
    while (low <= high) {
        int mid = (low + high) / 2;
        // if left most element is equal with right most and
        // middle element then we can reduce the search
        // space only by increasing the lower limit and
        // decreasing the upper limit
        if (arr[mid] == arr[low] && arr[mid] == arr[high]) {
            ans = Math.Min(ans, arr[mid]);
            low++;
            high--;
        }
        // If the left half is sorted, the minimum element
        // must be in the right half
        else if (arr[mid] > arr[high]) {
            low = mid + 1;
        }

        // If the right half is sorted, the minimum element
        // must be in the left half
        else {
            ans = Math.Min(ans,arr[mid]);
            high = mid - 1;
        }
    }

    // If no minimum element is found, return -1
    return ans;
  }

  // Driver program to test above functions
  public static void Main() {
    List<int> arr = new List<int> {5, 6, 1, 2, 3, 4};
    int N = arr.Count;
    Console.WriteLine("The minimum element is " + findMin(arr, 0, N - 1));
  }
}

// This code is contributed by Prajwal Kandekar
// This code is modified by Susobhan Akhuli
Javascript
function findMin(arr, low, high) {
  // If the array is not rotated
  if (arr[low] < arr[high]) {
    return arr[low];
  }
  
  let ans = Number.MAX_SAFE_INTEGER;

  // Binary search
  while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        
        // if left most element is equal with right most and
        // middle element then we can reduce the search
        // space only by increasing the lower limit and
        // decreasing the upper limit
        if (arr[mid] == arr[low] && arr[mid] == arr[high]) {
            ans = Math.min(ans, arr[mid]);
            low++;
            high--;
        }
        
        // If the left half is sorted, the minimum element
        // must be in the right half
        else if (arr[mid] > arr[high]) {
            low = mid + 1;
        }

        // If the right half is sorted, the minimum element
        // must be in the left half
        else {
            ans = Math.min(ans,arr[mid]);
            high = mid - 1;
        }
    }

    // If no minimum element is found, return -1
    return ans;
}

// Driver program to test above functions
let arr = [5,5,5,5,4,5];
let N = arr.length;
console.log("The minimum element is " + findMin(arr, 0, N - 1));

// This code is modified by Susobhan Akhuli

Output
The minimum element is 1


Time complexity: Worst Case: O(N) Average Case: O(logn)
Where n is the number of elements in the array. This is because the algorithm uses binary search, which has a logarithmic time complexity.
Auxiliary Space: O(1), the algorithm uses a constant amount of extra space to store variables such as low, high, and mid, regardless of the size of the input array.



Previous Article
Next Article

Similar Reads

Circularly Sorted Array (Sorted and Rotated Array)
Circularly sorted arrays are arrays that are sorted in ascending or descending order and then rotated by a number of steps. Let us take an example to know more about circularly sorted arrays: Consider an array: arr[] = {23, 34, 45, 12, 17, 19}The elements here, {12, 17, 19, 23, 34, 45} are sorted 'In-order' but they are rotated to the left by 3 tim
7 min read
Search an element in a sorted and rotated array with duplicates
Given an array arr[] which is sorted and rotated, the task is to find an element in the rotated array (with duplicates) in O(log n) time. Note: Print the index where the key exists. In case of multiple answer print any of them Examples: Input: arr[] = {3, 3, 3, 1, 2, 3}, key = 3 Output: 0 arr[0] = 3 Input: arr[] = {3, 3, 3, 1, 2, 3}, key = 11 Outpu
14 min read
Maximum element in a sorted and rotated array
Given a sorted array arr[] of distinct elements which is rotated at some unknown point, the task is to find the maximum element in it.Examples: Input: arr[] = {3, 4, 5, 1, 2} Output: 5Input: arr[] = {1, 2, 3} Output: 3 Approach: A simple solution is to traverse the complete array and find maximum. This solution requires O(n) time. We can do it in O
6 min read
Java Program for Search an element in a sorted and rotated array
An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time. Example: Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
9 min read
C++ Program for Search an element in a sorted and rotated array
An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.  Example:   Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3
7 min read
Python3 Program for Search an element in a sorted and rotated array
An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time. Example: Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
9 min read
C# Program for Search an element in a sorted and rotated array
An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.  Example:   Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3
7 min read
Php Program for Search an element in a sorted and rotated array
An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.  Example:   Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3
6 min read
Javascript Program for Search an element in a sorted and rotated array
An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.  Example:   Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3
7 min read
C Program for Search an element in a sorted and rotated array
An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.  Example:   Input : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3
4 min read
three90RightbarBannerImg