Find the Minimum in a Rotated Sorted Array

A sorted array rotated at some pivot is not sorted, so binary search cannot be applied directly, and yet the answer is still O(log n). The reason is that one half of any split is always still sorted, and that is enough to decide which side the minimum is on.

Written against Java 17.

The problem

Input:  [4, 5, 6, 7, 0, 1, 2]     rotated 4 times
Output: 0

Input:  [11, 13, 15, 17]          rotated 0 times
Output: 11

The minimum is the rotation point, the single place where an element is smaller than the one before it. Finding it also tells you how many positions the array was rotated by.

Why compare against the right end

static int findMin(int[] nums) {
    int low = 0, high = nums.length - 1;

    while (low < high) {
        int mid = low + (high - low) / 2;

        if (nums[mid] > nums[high]) {
            low = mid + 1;        // the minimum is strictly right of mid
        } else {
            high = mid;           // mid may itself be the minimum
        }
    }
    return nums[low];
}

Eight lines, and the comparison against nums[high] is the whole idea.

If nums[mid] > nums[high], the segment from mid to high must contain the wrap, because a sorted run cannot start higher than it ends. The minimum is therefore somewhere after mid, and mid itself is excluded, hence mid + 1.

If nums[mid] <= nums[high], the right half is sorted, so the minimum is at mid or to its left. mid cannot be excluded, because it may be the minimum itself, hence high = mid, not mid - 1.

Comparing against nums[low] does not work. On [3, 4, 5, 1, 2] with mid at index 2, nums[mid] = 5 > nums[low] = 3, which correctly suggests the left half is sorted. But on [1, 2, 3, 4, 5], no rotation, the same comparison holds and the conclusion “the minimum is to the right” is wrong. The left comparison cannot distinguish “not rotated” from “rotation point is to the right”; the right comparison can.

Why the loop uses <

while (low < high) rather than <=, and this pairs with high = mid.

The invariant is that the minimum is always inside [low, high], the loop shrinks that range and stops when it holds exactly one element, which is then the answer. With <=, the range never becomes empty: high = mid when low == high == mid assigns the same value and the loop spins forever.

This is the half-open discipline from the lower-bound formulation: high = mid and low < high go together, and high = mid - 1 and low <= high go together. Mixing them gives an infinite loop or a missed element.

Note that there is no return inside the loop and no equality branch. The array may contain no element equal to anything you can name in advance, so there is nothing to match on: the loop converges on a position rather than searching for a value.

Tracing it

On [4, 5, 6, 7, 0, 1, 2]:

low	high	mid	nums[mid]	nums[high]	comparison	action
0	6	3	7	2	7 > 2	low = 4
4	6	5	1	2	1 ≤ 2	high = 5
4	5	4	0	1	0 ≤ 1	high = 4
4	4	—	—	—	—	loop ends, return nums[4] = 0

Three iterations for seven elements. On the unrotated [11, 13, 15, 17] every comparison takes the else branch and high walks down to 0, returning the first element — which is correct without a special case for “not rotated”.

Duplicates break the guarantee

static int findMinWithDuplicates(int[] nums) {
    int low = 0, high = nums.length - 1;

    while (low < high) {
        int mid = low + (high - low) / 2;

        if (nums[mid] > nums[high])       low = mid + 1;
        else if (nums[mid] < nums[high])  high = mid;
        else                              high--;      // ambiguous — shrink by one
    }
    return nums[low];
}

When nums[mid] == nums[high] the comparison carries no information. [3, 3, 1, 3] and [3, 1, 3, 3] produce the same equality at the same position and have their minimum on opposite sides, so no O(1) decision is possible.

high-- is safe: nums[high] equals nums[mid], so discarding it cannot discard the only minimum — mid still holds the same value. But it removes only one element, so [3, 3, 3, 3, 3, 1] degenerates to O(n).

That is a proven lower bound rather than a weakness of this implementation. With duplicates, no algorithm can do better than linear in the worst case.

Finding the rotation count

The index of the minimum is the rotation count:

static int rotationCount(int[] nums) {
    int low = 0, high = nums.length - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[high]) low = mid + 1;
        else                        high = mid;
    }
    return low;                    // index, not value
}

Same loop, returning the index. An array rotated k times has its original element 0 at index k, which is what makes searching a rotated array possible in O(log n) — find the pivot, then binary search the correct half.

Checking it against a linear scan

The loop is short enough to look obviously right and subtle enough not to be, so the cheapest confidence comes from testing it against the brute-force answer over every rotation of every small array:

for (int n = 1; n <= 8; n++) {
    int[] base = IntStream.range(0, n).toArray();
    for (int k = 0; k < n; k++) {
        int[] rotated = rotate(base, k);
        assertEquals(0, findMin(rotated));            // the minimum of 0..n-1 is always 0
        assertEquals(k == 0 ? 0 : n - k, rotationCount(rotated));
    }
}

Exhaustive over the input space that matters, and it takes microseconds. Every off-by-one in this family of problems — the < against <=, the mid against mid - 1 — fails at n = 1 or n = 2, which is exactly the range a hand-written test tends to skip.

For the duplicate-tolerant version, generate arrays from a two-value alphabet: [1, 1, 1, 0, 1] and its rotations exercise the ambiguous branch far more densely than random data does.

Edge cases

• One element — the loop never runs and nums[0] is returned.
• Not rotated — handled without a special case, as traced above.
• Rotated by length — identical to not rotated.
• Two elements — one iteration; [2, 1] and [1, 2] both work.
• Empty array — nums.length - 1 is -1, the loop does not run, and nums[0] throws. Guard explicitly if empty input is possible; the algorithm has no meaningful answer for it.

The last one is the only genuine gap, and it is worth an explicit if rather than leaving an ArrayIndexOutOfBoundsException as the contract.

The transferable idea

The move here is worth naming because it recurs: in a rotated array, at least one half of any split is sorted, and identifying which one is a single comparison. Everything else follows.

The same reasoning drives searching for an arbitrary target in the array, finding the maximum (it is the element before the minimum), and checking whether the array is rotated at all. Each is the same loop with a different thing recorded.

More in the algorithms guides.

Frequently asked questions

Why compare the midpoint to the right end instead of the left?

The left comparison cannot distinguish an unrotated array from one whose rotation point is to the right. The right comparison can, because a sorted run never starts higher than it ends.

Why is it high = mid and not high = mid - 1?

mid may be the minimum. Excluding it can discard the answer.

Why does the loop use < rather than <=?

It pairs with high = mid. With <=, when low == high == mid the assignment changes nothing and the loop never terminates.

Do I need a special case for an unrotated array?

No. Every comparison takes the else branch and high converges on index 0, which is the correct answer.

What is the time complexity?

O(log n) with distinct elements, O(1) extra space. With duplicates the worst case is O(n).

Why do duplicates make it linear?

When nums[mid] == nums[high] the comparison is uninformative, and two arrays with the same values at those positions can have their minimum on opposite sides. The only safe move is to shrink by one.

Is high-- safe with duplicates?

Yes. nums[high] equals nums[mid], so discarding it cannot remove the only occurrence of the minimum.

How do I get the rotation count?

Return the index rather than the value. The minimum’s index is exactly how many positions the array was rotated.

How do I find the maximum?

It is the element immediately before the minimum — index (minIndex - 1 + n) % n.

What happens on an empty array?

The loop does not run and nums[0] throws. Guard it; there is no meaningful minimum of an empty array.