Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Find Minimum in Rotated Sorted Array

Find the smallest value in a rotated sorted array of distinct numbers in O(log n), by comparing the middle item with the right end at every step.

Updated Medium read: 8 min read

Approaches at a glance

ApproachTimeSpace
Scan every itemO(n)O(1)
Stop at the dropO(n)O(1)
Binary search against the right endO(log n)O(1)

The problem

An array of distinct integers was sorted in ascending order and then rotated: some number of items were moved from the front to the end, keeping their order. You are not told how many, and it may have been none.

Return the smallest value in the array. The solution must run in O(log n) time, which rules out looking at every item.

numbers = [11, 13, 15, 17, 2, 5, 8]   →  2
numbers = [3, 6, 9, 12]               →  3    (not rotated)
numbers = [9, 4]                      →  4
numbers = [7]                         →  7

Approach 1: scan every item

Forget that the array was ever sorted and keep the smallest value seen.

JavaScript

function findRotatedMinLinear(numbers) {
  let smallest = numbers[0];
  for (const value of numbers) {
    if (value < smallest) smallest = value;
  }
  return smallest;
}

Python

def find_rotated_min_linear(numbers):
    smallest = numbers[0]
    for value in numbers:
        if value < smallest:
            smallest = value
    return smallest

Time O(n). Space O(1). It gives the right answer for any array at all, which is exactly the problem: it uses nothing that is known about this one.

What rotation leaves behind

A rotated sorted array is two ascending runs joined together, and every value in the first run is larger than every value in the second.

[11, 13, 15, 17,   2, 5, 8]
 └── ascending ──┘ └ ascending ┘
                 ↑
            the only drop

There is one drop, a place where a value is followed by a smaller one, and the smallest value is the item straight after it. If the array was not rotated there is no drop, and the smallest value is the first item.

Approach 2: stop at the drop

That gives a slightly smarter scan. Walk along until a value is smaller than the one before it, and return it at once. If the walk reaches the end without finding a drop, the array was never rotated.

JavaScript

function findRotatedMinAtDrop(numbers) {
  for (let i = 1; i < numbers.length; i++) {
    if (numbers[i] < numbers[i - 1]) return numbers[i];
  }
  return numbers[0];   // no drop: the array is in order
}

Python

def find_rotated_min_at_drop(numbers):
    for i in range(1, len(numbers)):
        if numbers[i] < numbers[i - 1]:
            return numbers[i]
    return numbers[0]  # no drop: the array is in order

Time O(n) still. It can stop early, but when the drop is near the end, or absent, it reads everything. To do better the search must skip items, not walk past them.

Approach 3: binary search against the right end

Binary search needs a question about the middle item whose answer says which half to keep. Comparing the middle with a target is no use here, because there is no target. Compare it with the item at the right end of the range instead.

  • The middle is larger than the right end. Inside one ascending run, values further right are larger, so the middle and the right end cannot be in the same run. The middle is in the first run and the right end is in the second. The drop lies between them, so the smallest value is strictly to the right of the middle: lo = mid + 1.
  • The middle is smaller than the right end. From the middle to the right end there is no drop. Everything to the right of the middle is larger than it, so those items are out. The middle itself may be the smallest, so it stays: hi = mid.

The values are distinct and the middle is never the right end itself while the range has two or more items, so one of those two cases always applies.

JavaScript

function findRotatedMin(numbers) {
  let lo = 0;
  let hi = numbers.length - 1;
 
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
 
    if (numbers[mid] > numbers[hi]) {
      lo = mid + 1;   // the drop is to the right of mid
    } else {
      hi = mid;       // mid..hi is in order, so mid may be the smallest
    }
  }
  return numbers[lo];
}

Python

def find_rotated_min(numbers):
    lo = 0
    hi = len(numbers) - 1
 
    while lo < hi:
        mid = lo + (hi - lo) // 2
 
        if numbers[mid] > numbers[hi]:
            lo = mid + 1  # the drop is to the right of mid
        else:
            hi = mid  # mid..hi is in order, so mid may be the smallest
    return numbers[lo]

Throughout the loop one thing stays true: the smallest value is somewhere from lo to hi. Each branch removes only items that cannot be it. When lo and hi meet, one item is left, and that is the answer. The loop shape, lo < hi with hi = mid, is the lower-bound template used in Search Insert Position.

Walkthrough

numbers = [11, 13, 15, 17, 2, 5, 8]:

lo hi mid (value) Right end Middle larger? Action
0 6 3 (17) 8 Yes lo = 4
4 6 5 (5) 8 No hi = 5
4 5 4 (2) 5 No hi = 4
4 4 lo and hi have met Return numbers[4] = 2

And an array that was not rotated, [3, 6, 9, 12]:

lo hi mid (value) Right end Middle larger? Action
0 3 1 (6) 12 No hi = 1
0 1 0 (3) 6 No hi = 0
0 0 lo and hi have met Return numbers[0] = 3

No special case was needed. With no drop, the middle is never larger than the right end, so the range simply closes in on index 0.

Time O(log n): the range at least halves on every step. Space O(1).

Why not compare with the left end?

It seems symmetrical, but it is not. Suppose the middle is larger than the left end. Two different arrays fit:

[3, 6, 9, 12, 15]    middle 9 > left 3      smallest is at the LEFT
[9, 12, 15, 3, 6]    middle 15 > left 9     smallest is on the RIGHT

"The left part is in order" is true in both, yet the smallest value is inside that ordered part in one and outside it in the other. Code built on the left end has to check first whether the whole range is already sorted. The right end avoids this because of where the smallest value sits in an ordered stretch: at its left edge. Knowing that mid..hi is in order says the smallest value is at mid or before it. Knowing that lo..mid is in order says only that it is at lo or somewhere after mid.

Comparing the approaches

Scan every item Stop at the drop Binary search
Time O(n) O(n), may stop early O(log n)
Space O(1) O(1) O(1)
Looks at, for 1,000,000 items 1,000,000 Up to 1,000,000 About 20
Uses the sorted runs No A little Fully
Works with repeated values Yes Yes No

The last row matters. The binary search depends on the values being distinct. When repeats are allowed, the middle can equal the right end and neither case applies; Find Minimum in Rotated Sorted Array II deals with that.

The index where the loop ends is useful too: it is the number of places the array was rotated by. Returning lo in place of numbers[lo] gives the rotation point described in the rotated sorted arrays pattern, and Search in Rotated Sorted Array uses the same picture to find a target.

Try it yourself

Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.

JavaScript

console.log(findRotatedMin([11, 13, 15, 17, 2, 5, 8])); // 2
console.log(findRotatedMin([3, 6, 9, 12]));             // 3
console.log(findRotatedMin([9, 4]));                    // 4
console.log(findRotatedMin([7]));                       // 7

Python

print(find_rotated_min([11, 13, 15, 17, 2, 5, 8]))  # 2
print(find_rotated_min([3, 6, 9, 12]))  # 3
print(find_rotated_min([9, 4]))  # 4
print(find_rotated_min([7]))  # 7

The comment after each line is the result you should see.

Common mistakes

  • Writing hi = mid - 1. When the middle is not larger than the right end, the middle may be the smallest value. Removing it loses the answer: [9, 4]-style ranges and unrotated arrays go wrong.
  • Writing lo = mid. When the middle is larger than the right end it cannot be the smallest, and keeping it makes a two-item range loop for ever.
  • Looping while lo <= hi. With hi = mid, a range of one item never shrinks, so the loop never ends. This template stops when the bounds meet.
  • Comparing with the left end. It needs an extra check for a range that is already in order, as shown above.
  • Comparing with numbers[numbers.length - 1] out of habit. That happens to work for distinct values, but comparing with numbers[hi] is the version that carries over to the harder problems.
  • Sorting the array and taking the first item. It is correct and costs O(n log n), slower than even the plain scan.

Original problem: LeetCode 153: Find Minimum in Rotated Sorted Array