Find Minimum in Rotated Sorted Array — Practice

Problem

Given a rotated sorted array of unique elements, find the minimum element in O(log n) time.

Examples

Example 1

Input: nums = [3,4,5,1,2]

Output: 1

Explanation: The array was rotated so 1 (the original minimum) sits at index 3.

Example 2

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

Output: 0

Explanation: 0 is the minimum.

Constraints

•1 <= nums.length <= 5000
•All values are unique

Hints

Hint 1

The minimum element is exactly the 'pivot point' where the rotation happened — everything before it is >= the first element, everything from it onward is < the first element.

Hint 2

Compare nums[mid] against nums[right], not nums[left] — it gives a cleaner signal for which side the minimum is on.

Hint 3

If nums[mid] > nums[right], the minimum must be to the right of mid (the rotation point hasn't been passed yet); otherwise it's at or before mid.

Solutions

public int findMinBruteForce(int[] nums) {
    int min = nums[0];
    for (int n : nums) {
        min = Math.min(min, n);
    }
    return min;
}

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