Smallest value in a rotated sorted list

Compare the middle value with the last value. If the middle is bigger, the drop (and the minimum) is to its right; otherwise the minimum is at mid or to its left. Shrink towards it until lo meets hi. O(log n) time, O(1) space.

Comparing with the right end avoids a special case for lists that are not rotated at all.

With duplicates allowed, equal mid and right values force a linear step (hi -= 1), so the worst case becomes O(n).

The index of the minimum is also the rotation amount.

def rotated_min(vals: list[int]) -> int:
    lo, hi = 0, len(vals) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if vals[mid] > vals[hi]:
            lo = mid + 1  # the drop is to the right of mid
        else:
            hi = mid
    return vals[lo]

fun rotatedMin(vals: List<Int>): Int {
    var lo = 0
    var hi = vals.size - 1
    while (lo < hi) {
        val mid = (lo + hi) ushr 1
        if (vals[mid] > vals[hi]) lo = mid + 1 else hi = mid
    }
    return vals[lo]
}

Common mistakes

• Comparing with the left end and mishandling an unrotated list.
• Using hi = mid - 1 and skipping the minimum.

Explain why comparing with the right end is enough to decide the side.

Follow-up questions

Think of your answer first, then open the hint.

1. How do you search for a target in the rotated list?

   Show hint

   Find which half around mid is sorted and check whether the target falls in it.

2. What if duplicates are allowed?

   Show hint

   When vals[mid] == vals[hi], drop hi by one; worst case O(n).