Find Minimum In Rotated Sorted Array

The problem

nums started as a list of different integers sorted from smallest to largest. Then it was rotated: some of its values, possibly none, were moved from the front to the back, keeping their order. Return the smallest value in nums. Aim for O(log n) time, which means far fewer steps than looking at every value.

What to write

function solve(nums: number[]): number

Input
nums = [3,4,5,1,2]

Output
1

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

Output
0

Constraints

1–10,000 distinct integers; ascending array rotated any number of times.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Reading every value finds the smallest in n looks, but you are asked for O(log n): about 14 looks for 10,000 values. All you can lean on is the order. The list is a sorted list that was cut in two, with the pieces swapped, or not cut at all.

2. Hint 2: Ask a smaller question

   Pick any value in 4, 5, 6, 7, 0, 1, 2, for example the 6. Which one other value could you compare the 6 with to learn whether the smallest value comes before or after the 6?

3. Hint 3: Name the pattern

   Compare with the right end's value. A larger value sits in the first piece, so the smallest comes after that value. Any other value sits in the second piece, so the smallest is that value or an earlier one. Look in the middle and about half the range goes: binary search on a sorted range, here on two sorted pieces. Read the lesson on binary search on a sorted range.

4. Hint 4: State the invariant

   Keep a range of positions that always contains the smallest value. If the middle value is larger than the value at the right end, the smallest comes after the middle, so the middle goes too. Otherwise the middle might be the smallest, so the middle stays and everything after it goes.

5. Hint 5: Sketch the pseudocode

   low = 0, high = last position. While low < high: mid = (low + high) ÷ 2, rounded down. If the value at mid is larger than the value at high, low = mid + 1. Otherwise high = mid. When the loop ends, return the value at low.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Compare the midpoint with the right endpoint. A larger midpoint puts the minimum strictly to its right; otherwise keep the midpoint in the remaining interval.

The slow way

Walk through the list and remember the smallest value you have seen. This is correct and short, but it looks at all n values and makes no use of the order. The task asks for O(log n) time, which is far fewer looks than that.

The insight

After the rotation the list is two sorted pieces: first the larger values, then the smaller ones, which begin with the smallest value of all. If nothing was moved, the first piece is empty. So comparing a value with the value at the right end tells you its piece: larger means the first piece, smaller means the second.

Step by step

1. The smallest value is somewhere between the first and last position. Before any comparison, every position could hold the smallest value, so the range of possible positions is the whole list. Once one position is left there is nothing more to decide, so the loop stops there.
2. Compare the middle value with the value at the right end of the range. The right end of the range is always in the second piece, which begins with the smallest value. So a middle value larger than the right end's must be in the first piece, and a smaller one in the second.
3. The middle value is larger: the smallest is to its right. The middle is in the first piece, among the larger values, so the middle cannot be the smallest. The second piece, which begins with the smallest value, starts further right.
4. The middle value is smaller: the smallest is here or to its left. From the middle to the right end the values only climb, so no later value in the range is smaller than the middle value. The middle itself may be the smallest, so the middle stays in the range.
5. One position is left: it holds the smallest value. The range always held the smallest value and lost at least one position every round, so the one position left is where the smallest value sits.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. The smallest value is somewhere between the first and last position
  let l = 0,
    r = nums.length - 1;
  while (l < r) {
    // 2. Compare the middle value with the value at the right end of the range
    const m = Math.floor((l + r) / 2);
    if (nums[m] > nums[r]) {
      // 3. The middle value is larger: the smallest is to its right
      l = m + 1;
    } else {
      // 4. The middle value is smaller: the smallest is here or to its left
      r = m;
    }
  }
  // 5. One position is left: it holds the smallest value
  return nums[l];
}

function solve(nums: number[]): number {
  // 1. The smallest value is somewhere between the first and last position
  let l = 0,
    r = nums.length - 1;
  while (l < r) {
    // 2. Compare the middle value with the value at the right end of the range
    const m = Math.floor((l + r) / 2);
    if (nums[m] > nums[r]) {
      // 3. The middle value is larger: the smallest is to its right
      l = m + 1;
    } else {
      // 4. The middle value is smaller: the smallest is here or to its left
      r = m;
    }
  }
  // 5. One position is left: it holds the smallest value
  return nums[l];
}

def solve(nums):
    # 1. The smallest value is somewhere between the first and last position
    left, right = 0, len(nums) - 1
    while left < right:
        # 2. Compare the middle value with the value at the right end of the range
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            # 3. The middle value is larger: the smallest is to its right
            left = mid + 1
        else:
            # 4. The middle value is smaller: the smallest is here or to its left
            right = mid
    # 5. One position is left: it holds the smallest value
    return nums[left]

Example 2, traced

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

Output
0

Why it works

The range always contains the smallest value. A middle value larger than the right end's is in the first piece, so the middle and everything to its left can go. A smaller middle value is in the second piece, so everything to its right is larger and can go. The range shrinks every round until one position is left.

Time and space

Time O(log n), extra space O(1). Each round keeps about half of the range, and a list of n values can be halved about log n times: at most 14 rounds for 10,000 values. That is O(log n) time. Only the two ends and the middle are stored: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• When the middle value is smaller than the value at the right end, keep the middle in the range. In 4, 5, 1, 2, 3 the first middle value is the 1 itself. Stepping past the 1 returns 4.
• Compare with the right end, not the left end. In a list that was never rotated, such as 1, 2, 3, the middle is larger than the left end, so the search moves right and returns 3.
• Loop only while more than one position is left. With one position, the middle is that same position and the range cannot shrink, so a loop that keeps going never ends.

Pattern

Binary search on a sorted range. Builds on Binary Search and Koko Eating Bananas.

Keep going