blind-75

Find Minimum in Rotated Sorted Array

Best Case: The best case is when the minimum element is at index zero.
Worst Case: The worst case occurs when we need to search through most of the array.

Approach:

1. Use binary search to find the pivot point where rotation occurs.

Explanation to Interviewer:
“I would apply binary search by comparing middle elements with boundaries to efficiently locate the minimum element in logarithmic time.”

Code Implementation:

JavaScript:

function findMin(nums) {
    let left = 0,
        right = nums.length - 1;

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        
        if (nums[mid] > nums[right]) {
            left = mid + 1; // Minimum must be on right side.
        } else {
            right = mid; // Minimum could be mid or on left side.
        }
    }

    return nums[left];
}

const nums = [3,4,5,1,2];
console.log(findMin(nums)); // Output: 1

Python:

def find_min(nums):
    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]

nums=[3 ,4 ,5 ,1 ,2]
print(find_min(nums)) # Output: 1