Find Minimum in Rotated Sorted Array — Left Boundary on Rotation

Problem 311 · Find Minimum in Rotated Sorted Array

Difficulty: Medium · Pattern: Rotated Array (find pivot)

Intuition

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

Solutions

# Python
def findMin(nums):
    lo, hi = 0, len(nums)-1
    while lo < hi:
        mid = (lo+hi)//2
        if nums[mid] > nums[hi]: lo = mid+1  # min is in right half
        else: hi = mid                          # min is in left half or mid
    return nums[lo]

// Java
public int findMin(int[] nums) {
    int lo=0, hi=nums.length-1;
    while (lo<hi) {
        int mid=lo+(hi-lo)/2;
        if (nums[mid]>nums[hi]) lo=mid+1; else hi=mid;
    }
    return nums[lo];
}

// C++
int findMin(vector<int>& nums) {
    int lo=0, hi=nums.size()-1;
    while (lo<hi) { int mid=lo+(hi-lo)/2; if(nums[mid]>nums[hi]) lo=mid+1; else hi=mid; }
    return nums[lo];
}

Complexity

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