Find Minimum in Rotated Sorted Array — Binary Search O(log n) [Google, Microsoft]

Problem Statement

Given a sorted rotated array with unique elements, find the minimum.

Input: [3,4,5,1,2] → 1 Input: [4,5,6,7,0,1,2] → 0

Intuition
C++ Solution
Java / Python / JavaScript Solution
Complexity: O(log n) time, O(1) space

Intuition

If nums[mid] > nums[right], the minimum is in the right half. Otherwise it's in the left half (including mid).

C++ Solution

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

Java / Python / JavaScript Solution

def findMin(nums):
    l, r = 0, len(nums)-1
    while l < r:
        mid = (l+r)//2
        if nums[mid] > nums[r]: l = mid+1
        else: r = mid
    return nums[l]

Complexity: O(log n) time, O(1) space

With Duplicates: When nums[mid]==nums[r], can't determine direction → r--. Worst case O(n).