Find Minimum in Rotated Sorted Array — DSA

Problem

An array sorted in ascending order has been rotated some number of times: it was split at some point, and the two parts were swapped. For example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2].

Given such a rotated array of unique elements, return its minimum element, in O(log n) time.

Input: [3, 4, 5, 1, 2]          →   1
Input: [4, 5, 6, 7, 0, 1, 2]    →   0
Input: [11, 13, 15, 17]         →   11   (rotated a full cycle: already sorted)

The minimum is the rotation point: the only element smaller than the element before it.
The O(log n) requirement means a binary search that decides which half contains the rotation point.
Follow-up: Find Minimum in Rotated Sorted Array II allows duplicates, which breaks the O(log n) guarantee in the worst case.

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)