Developers

Find Minimum In Rotated Sorted Array

MediumBinary searchAlso known as LeetCode 153

A list of distinct integers was sorted in increasing order and then rotated: some number of its first elements were moved, in order, to the end. For example [0, 1, 2, 4, 5, 6, 7] rotated three times becomes [4, 5, 6, 7, 0, 1, 2]. A list that was rotated zero times, or a full length of times, is just sorted.

You get the rotated list. Return the smallest number in it. Aim for time that grows with log n.

Examples

Input nums = [3, 4, 5, 1, 2]
Output 1
Input nums = [4, 5, 6, 7, 0, 1, 2]
Output 0
Input nums = [11, 13, 15, 17]
Output 11
Not visibly rotated: the smallest is the first.

Constraints

  • 1 <= nums.length <= 5,000
  • -5,000 <= nums[i] <= 5,000
  • All values are distinct
  • nums is a sorted list rotated some number of times

Stuck? Take one hint at a time

Common mistakes
  • Comparing the middle with the left end, which fails when the list is already sorted.
  • Setting hi = mid - 1, which can skip over the minimum when mid itself is the answer.
  • Looping while lo <= hi with hi = mid, which never ends once the window has one position.
  • Forgetting the list that was not visibly rotated, where the answer is the first number.
Questions an interviewer may ask next
  • The list may contain duplicates. What goes wrong when nums[mid] equals nums[hi], and what do you do? (Shrink hi by one, which costs O(n) in the worst case.)
  • Find the number of times the list was rotated. (The position of the minimum.)
  • Search for a given target in the rotated list. (Search in Rotated Sorted Array.)
  • Why compare with the right end and not the left end? (The left end gives an ambiguous answer when the list is not visibly rotated.)