140. Find Minimum in Rotated Sorted Array

In a rotated sorted array, exactly one half of any [l, r] window is still sorted. Compare nums[mid] with nums[r] to tell which half contains the rotation point (the minimum).

• If nums[mid] > nums[r], the dip lies to the right of mid → go right.
• Otherwise, the dip is at mid or to the left → go left (keep mid).

Approach

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

Walk-through

nums = [4,5,6,7,0,1,2]

l == r == 4 → nums[4] = 0.

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