Find Minimum in Rotated Sorted Array

Concept

LeetCode #153.
Problem: Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in $O(\log n)$ time.

Input: nums = [4,5,6,7,0,1,2] -> Output: 0
Input: nums = [11,13,15,17] -> Output: 11 (Rotated 4 times, back to original)

This problem is closely related to “Search in Rotated Sorted Array”, but instead of looking for a specific target number, you are specifically hunting for the Pivot Point (the exact spot where the array breaks its sorted order and drops down to the minimum value).

The Strategy

If we look at [4, 5, 6, 7, 0, 1, 2].
The absolute minimum is 0.

To find it, we compare the middle element to the absolute right-most element.

• mid is 7. right is 2.
• Is 7 > 2? Yes.
• In a normal sorted array, the middle should NEVER be larger than the end. This mathematical anomaly proves that the “drop” (the pivot point) MUST be hiding somewhere to the right of mid! We aggressively discard the left side: left = mid + 1.

What if the array is [6, 0, 1, 2, 4, 5]?

• mid is 1. right is 5.
• Is 1 > 5? No. It’s properly sorted on the right side.
• This mathematically guarantees the drop is NOT to the right of mid. The minimum is either mid itself, or somewhere to its left. We aggressively discard the right side: right = mid.

Implementation

Notice that this algorithm uses the exact same while (left < right) template as “First Bad Version”. We are hunting for a boundary, so we do not use <= and we do not use mid - 1.

function findMin(nums: number[]): number {
    let left = 0;
    let right = nums.length - 1;

    // Use < to terminate when the pointers collide on the minimum value
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);

        // Does the middle value plunge down to the right?
        if (nums[mid] > nums[right]) {
            // The anomaly is on the right! The minimum is hiding over there.
            // Mid itself is massive, so we can safely discard it.
            left = mid + 1;
        } else {
            // The right side is perfectly sorted!
            // The anomaly must be to the left.
            // BUT, mid itself might be the absolute minimum, so we keep it!
            right = mid;
        }
    }

    // When Left and Right collide, they are sitting exactly on the minimum.
    return nums[left];
}

The Duplicates Edge Case

LeetCode #154. What if the array contains duplicates? [3, 3, 1, 3]

If left is 3, mid is 3, and right is 3…
Our algorithm checks nums[mid] > nums[right] (3 > 3). It’s False! It assumes the right side is perfectly sorted and jumps to the left (right = mid).
But the minimum (1) was hiding on the right side! The duplicates destroyed the logic.

The Fix:
If nums[mid] === nums[right], we have absolutely no mathematical idea which side the minimum is on. The only safe move is to shrink the search space by a single element to bypass the duplicate: right--.
This ensures we don’t accidentally skip the minimum, but it degrades the worst-case time complexity to $O(N)$ if the array is just [1, 1, 1, 1, 1].

Interview Questions

Q: In the algorithm, why do we compare nums[mid] to nums[right] instead of comparing it to nums[left]?
A: Let’s look at a completely sorted, non-rotated array: [1, 2, 3, 4].
If we compare to the left: nums[mid] (2) > nums[left] (1). The math tells us the left side is sorted, so the minimum must be on the left (right = mid). But right jumps to index 1 (2), completely skipping the true minimum (1) at index 0!
If we compare to the right: nums[mid] (2) > nums[right] (4) is False. The right side is sorted, so we jump left (right = mid). right lands on index 1 (2). Next loop, mid is 0 (1). nums[mid] > nums[right] is False. right = mid. right lands on index 0. We found the minimum! Comparing to right mathematically protects against the edge case of an already-sorted array.