☕ DSA Java Articles

Topics › Binary Search › BS on 1D Arrays

Find minimum in Rotated Sorted Array

Easy TUF ID 83 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

An array of n distinct integers was sorted in ascending order and then rotated between 1 and n times (rotating n times gives the original array back, so “not rotated” is included). Given the resulting array nums, return its minimum element in O(log n) time.

Constraints: 1 ≤ n ≤ 5000, all values distinct, values fit in a 32-bit signed integer.

Example 1

nums = [3, 4, 5, 1, 2]
answer = 1                // [1, 2, 3, 4, 5] rotated 3 times

Example 2

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

Example 3

nums = [11, 13, 15, 17]
answer = 11               // not rotated: the first element

Approach 1: Brute force, scan for the minimum

Intuition. The minimum of any array can be found by looking at every element once. This ignores the rotated-sorted structure entirely, so it is the fallback for arbitrary arrays and the oracle we test the fast versions against.

Algorithm.

  1. best = nums[0].
  2. For each value v, best = min(best, v).
  3. Return best.
static int bruteForce(int[] nums) {
    int best = nums[0];
    for (int v : nums) best = Math.min(best, v);
    return best;
}

Complexity. Time O(n), space O(1).

Approach 2: Optimal, take the minimum of the sorted half and discard it

Intuition. A rotated sorted array is two ascending runs; the minimum is the first element of the second run, right after the single “drop”. For any range [lo, hi] with midpoint mid, at least one half is sorted, and we can tell which: if nums[lo] <= nums[mid], the left half [lo, mid] is sorted, otherwise the right half [mid, hi] is.

A sorted half gives up its minimum for free: it is the half’s first element. So at each step we take the sorted half’s first element as a candidate for the answer, and then discard that half, because nothing else in it can be smaller than its first element. The unsorted half must contain the drop, so the true minimum is either the candidate we just recorded or somewhere in the unsorted half, which we keep searching.

A useful shortcut: if the whole current range is sorted (nums[lo] <= nums[hi]), its first element is its minimum and we can stop at once. This is what happens immediately for a non-rotated array.

Algorithm.

  1. lo = 0, hi = n - 1, ans = +infinity.
  2. While lo <= hi:
    • mid = lo + (hi - lo) / 2.
    • If nums[lo] <= nums[hi]: ans = min(ans, nums[lo]), stop.
    • Else if nums[lo] <= nums[mid]: ans = min(ans, nums[lo]), lo = mid + 1.
    • Else: ans = min(ans, nums[mid]), hi = mid - 1.
  3. Return ans.
static int optimal(int[] nums) {
    int lo = 0, hi = nums.length - 1, ans = Integer.MAX_VALUE;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[lo] <= nums[hi]) {              // whole range sorted: its first element is the smallest
            ans = Math.min(ans, nums[lo]);
            break;
        }
        if (nums[lo] <= nums[mid]) {             // left half sorted: nums[lo] is its minimum, drop it
            ans = Math.min(ans, nums[lo]);
            lo = mid + 1;
        } else {                                 // right half sorted: nums[mid] is its minimum, drop it
            ans = Math.min(ans, nums[mid]);
            hi = mid - 1;
        }
    }
    return ans;
}

Dry run on nums = [4, 5, 6, 7, 0, 1, 2]:

lo hi mid nums[lo] <= nums[hi]? sorted half candidate action
0 6 3 4 <= 2? no left (4 <= 7) ans = 4 lo = 4
4 6 5 0 <= 2? yes whole range ans = min(4, 0) = 0 stop

Complexity. Time O(log n): each iteration discards about half of the range. Space O(1).

Two remarks on ans. It starts at Integer.MAX_VALUE, which is safe even if the array’s minimum is Integer.MAX_VALUE (a one-element array), because min(MAX_VALUE, MAX_VALUE) is still the right answer. And every value assigned to ans is a real element of the array, so the method never invents a value.

Approach 3: Optimal, compare mid with the right end

Intuition. There is a tighter formulation that needs no ans variable. Compare nums[mid] with nums[hi]:

The invariant “the minimum is in [lo, hi]” holds throughout, the range strictly shrinks each step, and when lo == hi that single index must be the minimum.

Why compare with nums[hi] rather than nums[lo]? Comparing with the left end is ambiguous: for a non-rotated array nums[mid] > nums[lo] and the minimum is on the left, but for [5, 6, 7, 1, 2] also nums[mid] > nums[lo] while the minimum is on the right. The right end does not have this problem because the minimum always sits in the run that ends at hi.

Algorithm.

  1. lo = 0, hi = n - 1.
  2. While lo < hi: mid = lo + (hi - lo) / 2; if nums[mid] > nums[hi], lo = mid + 1; else hi = mid.
  3. Return nums[lo].
static int optimalCompareRight(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;  // the drop is strictly right of mid
        else hi = mid;                           // nums[mid] < nums[hi]: minimum is mid or left of it
    }
    return nums[lo];
}

Dry run on nums = [3, 4, 5, 1, 2]:

lo hi mid nums[mid] nums[hi] action
0 4 2 5 2 5 > 2: lo = 3
3 4 3 1 2 1 < 2: hi = 3
3 3       lo == hi: return nums[3] = 1

Complexity. Time O(log n), space O(1).

Note the asymmetry lo = mid + 1 versus hi = mid: when nums[mid] > nums[hi], mid is definitely not the minimum, so it is excluded; when nums[mid] < nums[hi], mid might be the minimum, so it must stay. Because mid < hi whenever lo < hi, setting hi = mid always shrinks the range and the loop terminates.

Edge cases and pitfalls