Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in O(log N) time. You may assume the array does not contain duplicates.

To find the minimum element in a rotated sorted array in O(log⁡N)O(\log N)O(logN) time, you can use a modified binary search approach. The key observation is that even though the array is rotated, one part of the array will still be in sorted order. By comparing elements in the middle of the array with the start and end, you can determine which half of the array contains the minimum element.

Steps:

1. If the middle element is greater than the last element, then the smallest element must be in the right half.
2. If the middle element is less than the last element, then the smallest element is in the left half, including the middle element itself.
3. Continue narrowing down the search space until you find the minimum element.

Here’s the implementation of this approach:

For example, given [5, 7, 10, 3, 4], return 3.

Python

deffind_min(nums):
    left, right = 0, len(nums) - 1while left < right:
        mid = (left + right) // 2# Compare middle element with the rightmost elementif nums[mid] > nums[right]:
            # Minimum is in the right half
            left = mid + 1else:
            # Minimum is in the left half including mid
            right = mid
    
    return nums[left]

# Example usage
arr = [5, 7, 10, 3, 4]
print(find_min(arr))  # Output: 3

Javascript

functionfindMin(nums) {
    let left = 0, right = nums.length - 1;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        // Compare middle element with the rightmost elementif (nums[mid] > nums[right]) {
            // Minimum is in the right half
            left = mid + 1;
        } else {
            // Minimum is in the left half including mid
            right = mid;
        }
    }
    
    return nums[left];
}

// Example usageconst arr = [5, 7, 10, 3, 4];
console.log(findMin(arr));  // Output: 3

Java

publicclassMain {
    publicstaticintfindMin(int[] nums) {
        intleft=0, right = nums.length - 1;
        
        while (left < right) {
            intmid= (left + right) / 2;
            
            // Compare middle element with the rightmost elementif (nums[mid] > nums[right]) {
                // Minimum is in the right half
                left = mid + 1;
            } else {
                // Minimum is in the left half including mid
                right = mid;
            }
        }
        
        return nums[left];
    }

    publicstaticvoidmain(String[] args) {
        int[] arr = {5, 7, 10, 3, 4};
        System.out.println(findMin(arr));  // Output: 3
    }
}