Solution For Find Minimum In Rotated Sorted Array

The problem “Find Minimum in Rotated Sorted Array” on LeetCode can be solved efficiently using the Binary Search algorithm. The problem statement is as follows:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in the array.

You may assume no duplicate exists in the array.

Example 1:
Input: [3,4,5,1,2] Output: 1

Example 2:
Input: [4,5,6,7,0,1,2] Output: 0

To solve this problem, we can make use of Binary Search algorithm by finding the pivot element. The pivot element is the minimum element in the array and it is the element that is the result of rotation of the original sorted array.

The approach to solve this problem is as follows:

1. Initialize left and right pointers to the start and end of the array respectively.
2. While the left pointer is less than the right pointer, compute the mid value as (left + right) / 2.
3. If the mid value is greater than the element at the right pointer, then shift the left pointer i.e., left = mid + 1.
4. Otherwise, shift the right pointer i.e., right = mid.
5. Once the while loop terminates, the minimum element will be at the left pointer.

The implemented code in Python is as follows:

class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) – 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]

Step by Step Implementation For Find Minimum In Rotated Sorted Array

class Solution {
    public int findMin(int[] nums) {
        
        // check for empty or null array
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        // initialize left and right pointers
        int left = 0;
        int right = nums.length - 1;
        
        // if the array is not rotated, the minimum element will be the first element
        if (nums[left] < nums[right]) {
            return nums[left];
        }
        
        // binary search for the minimum element
        while (left <= right) {
            // find the midpoint
            int mid = left + (right - left) / 2;
            
            // if the midpoint is the minimum element, return it
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }
            // if the midpoint is greater than the first element, that means the minimum element is still to the right
            else if (nums[mid] > nums[left]) {
                left = mid + 1;
            }
            // if the midpoint is less than the first element, that means the minimum element is to the left
            else {
                right = mid;
            }
        }
        
        // the minimum element was not found
        return -1;
    }
}

# Solution 1:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        # Base case
        if len(nums) == 1:
            return nums[0]
        
        # General case
        left = 0
        right = len(nums) - 1
        
        # Check if the array is already sorted
        if nums[right] > nums[left]:
            return nums[left]
        
        # Perform binary search
        while left <= right:
            # Find the middle element
            mid = left + (right - left) // 2
            
            # Check if the middle element is the minimum element
            if nums[mid] > nums[mid + 1]:
                return nums[mid + 1]
            
            # Check if the middle element is greater than the first element
            # This means the minimum element is still to the right of the middle element
            if nums[mid] >= nums[left]:
                left = mid + 1
            
            # Otherwise, the minimum element is to the left of the middle element
            else:
                right = mid

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    
};

class Solution {
public:
    int findMin(vector& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};

public int FindMin(int[] nums) { // check for empty or null array if (nums == null || nums.Length == 0) { return -1; } // set left and right indices int left = 0; int right = nums.Length - 1; // loop until left index passes right index while (left <= right) { // calculate middle index int middle = left + (right - left) / 2; // if middle element is greater than element to its right, // the minimum must be to the right of the middle element if (nums[middle] > nums[middle + 1]) { return nums[middle + 1]; } // if middle element is less than element to its left, // the minimum must be to the left of the middle element if (nums[middle] < nums[middle - 1]) { return nums[middle]; } // if neither of the above is true, // the array is not rotated and the minimum is the first element if (nums[left] <= nums[middle]) { // if the first element is less than or equal to the middle element, // the minimum cannot be to the left of the first element, so move the left index to the right left = middle + 1; } else { // if the first element is greater than the middle element, // the minimum cannot be to the right of the middle element, so move the right index to the left right = middle - 1; } } // if the left index passes the right index, the minimum is the first element return nums[0]; }