A replica keeps a strictly increasing array of committed sequence numbers. After a failover, the in-memory copy is a rotation of that list: one increasing run, a drop, then another increasing run. Ops wants the smallest sequence still live so they can drop everything older. The first version scanned for min. A few thousand numbers returned instantly. After the WAL grew to tens of millions of stamps, the health check was still walking when the probe timed out.

The drop between the two increasing runs is the minimum. An array already gives a[i] for free. A scan uses that and still pays O(n). Unique values and one rotation mean there is exactly one drop to chase.

This is an interview writeup, not a procedure lecture. The binary search post owns the invariant and mid overflow. The membership writeup is the unrotated cousin: one sorted slice, return an index or -1. Here the range is two sorted runs. We only chase which side of mid still contains the drop.

The problem

Given a unique, strictly increasing int[] nums that has been rotated between 0 and n times, return the minimum value. Typical interviews want O(log n) time.

nums = [4, 5, 6, 7, 0, 1, 2]  →  0
nums = [3, 4, 5, 1, 2]        →  1
nums = [11, 13, 15, 17]       →  11

Note: A rotation of 0 is legal. The array is still sorted, there is no drop, and the minimum is nums[0]. The loop must still terminate there. Do not assume a wrap always exists.

Linear min is the honest brute force

Every index is compared once. Correct. Linear.

int findMinScan(int[] nums) {
    int min = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < min) {
            min = nums[i];
        }
    }
    return min;
}

At n = 20 this is a rounding error. At n in the tens of millions you paid a full walk for a question a one-drop range answers in a handful of probes: which side of mid still holds the drop?

Binary search vs nums[hi]: chase the drop

Keep inclusive bounds, but stop when one slot remains: while (lo < hi). Mid is lo + (hi - lo) / 2. Compare nums[mid] to nums[hi], not to nums[lo]. Comparing to lo needs a separate “already sorted” check; hi makes that case the same branch as “min is mid or left.”

  • If nums[mid] > nums[hi], mid sits in the left (larger) run. The drop is strictly right of mid: lo = mid + 1.
  • Otherwise the slice through hi is still non-decreasing, so the min is mid or left of it: hi = mid. Do not drop mid; it may be the answer.

lo == hi means the remaining slot is the minimum. Return nums[lo].

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

lo=0 hi=6 mid=3  nums[3]=7  7>2  drop is right of mid  → lo=4
lo=4 hi=6 mid=5  nums[5]=1  1<2  min is mid or left    → hi=5
lo=4 hi=5 mid=4  nums[4]=0  0<1  min is mid or left    → hi=4
lo=4 hi=4  done — return nums[4]=0

The Java is that loop:

int findMin(int[] nums) {
    int lo = 0;
    int hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return nums[lo];
}

Time is O(log n) — each comparison throws away half the remaining range. Space is O(1) — two indices, no extra table. Mid overflow already lives on the algorithms post; do not re-lecture it unless they ask.

Note: This loop uses while (lo < hi) and hi = mid. Mid is still a candidate. The membership writeup’s inclusive while (lo <= hi) must drop mid on every miss; copying hi = mid onto that contract never terminates when lo == hi.

What interviewers usually poke next

  • No rotation. Already sorted. On unique values nums[mid] is never greater than nums[hi], so hi walks toward 0 and you return nums[0]. Name the case; the same loop handles it.
  • Duplicates. If nums[mid] == nums[hi], you cannot tell which side holds the drop. Shrinking hi by one is honest and worst-case linear. The unique-values license is gone; say so.
  • Search for a target. Search in a Rotated Sorted Array is the sibling: decide which half is still sorted, then whether the target lives there. This problem only chases the drop. One loop does not answer both.
  • Empty / null. The prompt promised a non-empty unique array. In production you would reject; at the board, ask.

You are done with this problem when you can say, out loud, why the linear min is correct, why one drop licenses discarding a half, and why hi = mid on the “min is mid or left” branch.