Find Minimum in Rotated Sorted Array

medium

Find the minimum element in a sorted array that has been rotated

Find Minimum in Rotated Sorted Array

Key Insight

If arr[mid] > arr[right], the minimum is in the right half (rotation point is there). Otherwise, it is in the left half including mid.

Step 1Initialize
Find rotation point (minimum)
L
R
3
0
4
1
5
2
1
3
2
4
Search space: [0..4]

Rotated sorted array. Minimum is at the rotation point.

1 / 5

Learn the Pattern

Binary SearchEliminate half the search space each iteration by comparing the midpoint against a condition, reducing O(n) linear scans to O(log n).
Practice the Code

Step-by-Step Walkthrough: Find Minimum in Rotated Sorted Array

If arr[mid] > arr[right], the minimum is in the right half (rotation point is there). Otherwise, it is in the left half including mid.

  1. Initialize

    Rotated sorted array. Minimum is at the rotation point.

  2. Mid=2, arr[2]=5

    arr[2]=5 > arr[4]=2. Minimum must be in right half.

  3. Narrow Right

    left=3, right=4, mid=3, arr[3]=1. arr[3]=1 <= arr[4]=2. Min is at mid or left of mid.

  4. Converged

    right=3, left=3. Pointers converge. arr[3]=1 is the minimum.

  5. Result

    Minimum is 1 at index 3 (the rotation point).