Articles by FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
Articles by FavTutor
No Result
View All Result
Home Data Structures and Algorithms

Find Minimum in Rotated Sorted Array (with Solution)

Jatin Chanana by Jatin Chanana
January 9, 2024
Reading Time: 6 mins read
Find Minimum in Rotated Sorted Array
Follow us on Google News   Subscribe to our newsletter

There are many leetcode problems associated with arrays that are being asked in interviews, one of them is finding the minimum in the rotated sorted array. This article will delve into the various approaches to finding the minimum element in a rotated sorted array, with code implementation.

Find Minimum in the Rotated Sorted Array Problem

In the programming problem to find the minimum in the rotated sorted array, we are given a sorted array that has been rotated between 1 and n times. Our task is to find the minimum element in this rotated sorted array. It is important to note that all elements in the array are unique.

Rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Let us understand it with an example:

Input: nums = [3,4,5,1,2]
Output: 1

Note that the original array was [1,2,3,4,5] rotated 3 times.

Let’s discuss the easy solution using linear search. In this approach of finding the minimum element, we will traverse the whole array from start to end comparing each element to find the minimum. Here are the steps involved:

  • First of all, we will declare a variable to store the minimum element and initialize it with the first element of the array
  • Now we will start traversing from 2nd element to the last and compare each element with the minimum element. If a smaller element is found, we will update the minimum element
  • After traversing the entire array, the minimum element will be stored in the variable
  • Now we will return the minimum element.

The Time Complexity of this approach is O(N), where n is the size of the array. The Space Complexity is O(1) as we haven’t used any extra space.

Using Binary Search to Solve It

The best possible way to find the minimum in a rotated sorted array is by using Binary Search. We know that we can apply binary search in a sorted array and a rotated sorted array. We have two sorted halves and we have to detect in which half minimum element is present.

Binary Search and Linear Search are the two most used searching algorithms in any programming language.

Let’s do it step-by-step:

  • Firstly we will initialize two variables ‘low’ and ‘high’ to the first and last indices of the array and mid is calculated as the middle index using the formula ‘low + (high-low)/2’.
initialize two variables ‘low’ and ‘high’
  • ‘ans’ is initialized to INT_MAX to keep track of the minimum element.
  • Now we will run a while loop as long as ‘low’ is less than or equal to ‘high’.
  • Inside the loop, we will check whether the segment of the array from ‘low’ to ‘mid’ is sorted, by checking nums[low]<=nums[mid] (3<=5).
  • If true we will update ‘ans’ with the minimum of current ‘ans’ and ‘nums[low]’ and adjust the search range by updating ‘low’ to ‘mid+1’.
Update ans and range
  • If the segment is not sorted, it means the rotation point is in the current segment. It updates ans with the minimum of the current ans and nums[mid] and adjusts the search range by updating ‘high’ to ‘mid-1’.
  • The mid is then recalculated using the formula low + (high – low) / 2.
  • The loop continues until the low is greater than the high, at which point the search range has converged

C++ Code

Let’s implement it in C++:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int findMin(vector<int>& nums) {
    int n = nums.size();
    int low = 0;
    int high = n - 1;
    int mid = low + (high - low) / 2;
    int ans = INT_MAX;

    while (low <= high) {
        if (nums[low] <= nums[mid]) {
            ans = min(ans, nums[low]);
            low = mid + 1;
        } else {
            ans = min(ans, nums[mid]);
            high = mid - 1;
        }
        mid = low + (high - low) / 2;
    }

    return ans;
}

int main() {
    vector<int> rotatedArray = {3,4,5,1,2};
    int minElement = findMin(rotatedArray);

    cout << "Minimum Element: " << minElement << endl;

    return 0;
}

Python Code

We can do the binary search approach in Python as well:

def find_min(nums):
    n = len(nums)
    low = 0
    high = n - 1
    ans = float('inf')

    while low <= high:
        mid = low + (high - low) // 2

        if nums[low] <= nums[mid]:
            ans = min(ans, nums[low])
            low = mid + 1
        else:
            ans = min(ans, nums[mid])
            high = mid - 1

    return ans

rotated_array = [3, 4, 5, 1, 2]
min_element = find_min(rotated_array)
print("Minimum Element:", min_element)

Java Code

Finally, here is the Java program to find minimum in rotated sorted array:

import java.util.Arrays;

public class FindMin {

    public static int findMin(int[] nums) {
        int n = nums.length;
        int low = 0;
        int high = n - 1;
        int ans = Integer.MAX_VALUE;

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

            if (nums[low] <= nums[mid]) {
                ans = Math.min(ans, nums[low]);
                low = mid + 1;
            } else {
                ans = Math.min(ans, nums[mid]);
                high = mid - 1;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] rotatedArray = {3, 4, 5, 1, 2};
        int minElement = findMin(rotatedArray);
        System.out.println("Minimum Element: " + minElement);
    }
}

Output:

Minimum Element: 1

The time complexity is O(log N), where N is the size of the input array nums. The binary search algorithm is used to find the minimum element, and in each iteration, the search range is effectively halved. The Space complexity is O(1) as we haven’t used any extra space.

Before ending this tutorial, let’s compare both the approaches:

Approach Time complexitySpace complexityDetails 
Linear search
Approach
O(N)O(1)As we are traversing through the array only once to check the minimum element.
Binary search ApproachO(Nlogn)O(1)The binary search algorithm is used to find the minimum element, and in each iteration, the search range is effectively halved.

Conclusion

In conclusion, the leetcode problem of finding the minimum element in a rotated sorted array has been addressed through both a brute-force linear search and an optimized binary search approach, with their time complexity and space complexity and implementation in C++, Java, and Python.

ShareTweetShareSendSend
Jatin Chanana

Jatin Chanana

I am Jatin, a final-year undergraduate student with a keen interest in the field of software development. I possess a strong academic background and a deep passion for Data Structures, Algorithms, and Web Development.

RelatedPosts

validate ip address

Validate IP Address Problem ( C++, JAVA, Python)

April 3, 2025
Shortest Palindrome Problem

Shortest Palindrome Problem ( C++, JAVA, Python)

April 4, 2025
Zigzag Conversion Problem

Zigzag Conversion Problem (C++, Java, Python)

April 4, 2025
Next Right Pointers In Each Node

Populating Next Right Pointers In Each Node (with code)

March 27, 2024
Coin Change II

Coin Change II Problem (C++, Java, Python)

April 7, 2025

About FavTutor

FavTutor is a trusted online tutoring service to connects students with expert tutors to provide guidance on Computer Science subjects like Java, Python, C, C++, SQL, Data Science, Statistics, etc.

Categories

  • AI News, Research & Latest Updates
  • Trending
  • Data Structures
  • Web Developement
  • Data Science

Important Subjects

  • Python Assignment Help
  • C++ Help
  • R Programming Help
  • Java Homework Help
  • Programming Help

Resources

  • About Us
  • Contact Us
  • Editorial Policy
  • Privacy Policy
  • Terms and Conditions

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.

No Result
View All Result
  • AI News
  • Data Structures
  • Web Developement
  • AI Code Generator
  • Student Help
  • Main Website

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.