DSA Factory
Free Binary search lessonsBinary search · Stage 3 · Rotated and peaks · Step 2

Where the sorted list wraps around

A sorted list was rotated, so find its smallest value by comparing the middle with the last value. About 14 minutes.

Which run is the middle in

A rotated sorted list (with all values different) has a big run first, such as 4, 5, 6, 7, followed by a small run, 0, 1, 2. Every value in the big run is larger than every value in the small run, and the smallest overall is the first value of the small run.

Compare the middle value with the last value. If the middle is bigger, it is in the big run, so the wrap is to its right. If it is smaller, it is in the small run, so the smallest is the middle itself or something to its left.

Middle bigger than last: the wrap is to the right.
Middle smaller than last: the smallest is here or to the left.
In code
if nums[mid] > nums[high]:
    print("the drop is to the right")
else:
    print("the drop is at mid or left")
Find the smallest in a rotated sorted list.
6
0
7
1
9
2
1
3
2
4
3
5
4
6
leftright

The middle is 1, and the last value is 4. 1 is not bigger, so the smallest is here or to the left.

Move 1 of 4

Already sorted is fine

If the list was rotated by nothing, it is plain sorted and the smallest is the first value. The same search handles it: the middle is never bigger than the last value, so high keeps moving to the middle until it reaches position 0.

Notice we compare with the last value rather than the first. Comparing with the first value can't tell a sorted list from a rotated one, which is why the last value is the right yardstick.

Last value: is always in the small run.
First value: can mislead when nothing was rotated.
Quick check

In a rotated list the middle value is 3 and the last value is 9. Where is the smallest?

  1. AAt the middle or to its left, because 3 isn't bigger than 9
  2. BTo the right of the middle
  3. CAt the last position
Show the answer

At the middle or to its left, because 3 isn't bigger than 9. A middle that's not above the last value is in the small run.

Your problem

Smallest in a rotated list

nums is a list of different whole numbers that was sorted from smallest to largest and then rotated, meaning some number of values from the front were moved to the back in the same order (possibly none). Return the smallest value.

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

1 ≤ length ≤ 100,000 · −1,000,000,000 ≤ value ≤ 1,000,000,000 · all values different

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve