Find minimum in Rotated sorted Array

153.Find Minimum in Rotated Sorted Array

Array

Binary Search

Divide and Conquer

Problem Statement:

Given a sorted array that is rotated at some pivot point, find the minimum element. The array does not contain duplicates.

Example:

Input:

nums = [3,4,5,1,2]

→

Output:

1

Original array was [1,2,3,4,5], rotated 3 times

Algorithm:

1. Check if mid is pivot by comparing with neighbors
2. Compare mid with endpoints to identify sorted portion
3. Move towards unsorted portion
4. Handle case when array is fully sorted

Complexity:

Time: O(log n) | Space: O(1)

Java Solution:

// This is my amazing solution I came up with myself after MUCH DELIBERATION
// Features: Mid check
// Normal searching
public int findMin(int[] nums) {
    int low = 0, high = nums.length - 1;
    
    while (low <= high) {
        int mid = (low + high)/2;
        
        if (mid > 0 && nums[mid] < nums[mid - 1]) return nums[mid];
        if (mid < nums.length - 1 && nums[mid + 1] < nums[mid]) return nums[mid + 1];
        
        if (nums[mid] > nums[high])  // right unsorted, def not mid
            low = mid + 1;
        else if (nums[low] > nums[mid])  // left unsorted, could be mid (so dont do mid - 1)
            high = mid - 1;
        else return nums[low];  // Both parts of array are sorted, nums[low] is answer (DONT FORGET THIS CASE)
    }
    
    return -1;
}

Python Solution:

def findMin(self, nums: List[int]) -> int:
    low, high = 0, len(nums) - 1
    
    while low <= high:
        mid = (low + high) // 2
        
        # Check if mid is pivot
        if mid > 0 and nums[mid] < nums[mid - 1]:
            return nums[mid]
        if mid < len(nums) - 1 and nums[mid + 1] < nums[mid]:
            return nums[mid + 1]
        
        # Search in unsorted portion
        if nums[mid] > nums[high]:
            low = mid + 1
        elif nums[low] > nums[mid]:
            high = mid - 1
        else:
            return nums[low]
        
    return -1

C++ Solution:

int findMin(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    
    while (low <= high) {
        int mid = low + (high - low)/2;
        
        // Check if mid is pivot
        if (mid > 0 && nums[mid] < nums[mid - 1])
            return nums[mid];
        if (mid < nums.size() - 1 && nums[mid + 1] < nums[mid])
            return nums[mid + 1];
        
        // Search in unsorted portion
        if (nums[mid] > nums[high])
            low = mid + 1;
        else if (nums[low] > nums[mid])
            high = mid - 1;
        else
            return nums[low];
    }
    
    return -1;
}