LeetCode 153 · Medium · Binary Search

Find Minimum in Rotated Sorted Array

A sorted array of distinct integers was rotated: some tail of it was moved to the front. Return its smallest value in O(log n) time.

O(log n)time
O(1)space
m vs rwhich side holds the drop

1–16 distinct integers, −99 to 99 · a sorted list rotated any number of times

public int findMin(int[] nums) { int l = 0; int r = nums.length - 1; while (l < r) { // the min is always in [l, r] int m = l + (r - l) / 2; if (nums[m] > nums[r]) { l = m + 1; // the drop is right of m } else { r = m; // m..r rises; m may be the min } } return nums[l];}
l
—
r
—
m
—
nums[m]
—
nums[r]
—

Why it works

  1. A linear scan finds the min in O(n), or finds the one place where a value is smaller than the one before it. Neither uses the fact that both pieces are sorted.
  2. Compare the middle with the right end. If nums[m] > nums[r], the values must drop somewhere after m, and the min is that drop: it lies in [m+1, r]. Otherwise m..r rises steadily, so nothing right of m beats nums[m]: keep [l, m]. Invariant: the min is always inside [l, r].
  3. O(log n) time, O(1) space. Each comparison throws away about half of [l, r]; the loop stops when one cell remains, and that cell is the min.
  4. Pitfall: r = m, not m - 1. In the rising case nums[m] may be the min itself, so it must stay. That is also why the loop runs while l < r: with l <= r and r = m it never ends. Comparing with nums[l] instead fails on an array that is not rotated.
  5. Related: Search in Rotated Sorted Array (33) uses the same "one side is sorted" test to find a target. With duplicates (154), nums[m] == nums[r] tells you nothing, so drop r by one; the worst case becomes O(n).