DSA With AI
Week 2 ยท Binary Search

Find Minimum in Rotated Sorted Array

Find the minimum value in a sorted array that was rotated, with no duplicates.

Medium Binary Search Week 2 Practice runner

Frame the problem

  • The array contains no duplicates in the standard version.
  • The array may be rotated zero times.
  • Target time is O(log n).
1. Reveal example inputs and outputs

Example 1

Input:

find_min([
  3,
  4,
  5,
  1,
  2
])

Output:

1

Example 2

Input:

find_min([
  11,
  13,
  15,
  17
])

Output:

11
2. Brute force first

A linear scan is easy; what sorted-half signal lets binary search discard half the array?

3. Reveal the insight ladder
  1. Compare nums[mid] with nums[right].
  2. If nums[mid] > nums[right], the minimum is to the right of mid.
  3. Otherwise, the minimum is at mid or to the left.
  4. Converge left and right to the minimum index.
4. Dry run before code
  1. nums = [3, 4, 5, 1, 2].
  2. mid is 5, which is greater than right value 2, so min is right of mid.
  3. Converge to index 3, value 1.
5. Reveal final Python solution 
def find_min(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

Complexity: Time O(log n), space O(1).

Interview narration

  • The right boundary tells me whether mid is in the left sorted segment or the minimum segment.
  • I keep mid when it might be the minimum.
  • The loop ends when both pointers name the minimum.

Common traps

  • Dropping mid when it could be the minimum.
  • Using left <= right and creating off-by-one exits.
  • Forgetting the non-rotated case.

Follow-up drills

1. What changes if duplicates are allowed?

When nums[mid] == nums[right], you cannot know which side contains the minimum, so you can decrement right. Worst-case time degrades to O(n).

2. Why compare to right instead of left?

Comparing to right cleanly identifies whether mid is in the high left segment; comparing to left can work but often has more cases.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.