153. Find Minimum in Rotated Sorted Array

Edited by Charles

Medium · Python · Array

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

You are given a sorted array of unique elements that has been rotated between 1 and n times.

Original study notes follow, including intermediate snippets and earlier attempts.

Problem

You are given a sorted array of unique elements that has been rotated between 1 and n times.

For example, the original sorted array:

[0, 1, 2, 4, 5, 6, 7]

may become:

[4, 5, 6, 7, 0, 1, 2]

Return the minimum element of the array.

The solution must run in:

O(log n)

time.

Because the original array is sorted and all elements are unique, after rotation the array consists of two sorted parts.

For example:

[4, 5, 6, 7, 0, 1, 2]

 ↑        ↑  ↑     ↑
 sorted part  sorted part

The minimum element is exactly the rotation point:

[4, 5, 6, 7, 0, 1, 2]
             ↑
           minimum

We can use Binary Search to locate this point.

Key Idea

At every step, compare:

nums[mid]

with:

nums[right]

There are two cases.

Case 1 — nums[mid] > nums[right]

If:

nums[mid] > nums[right]

then the minimum must be strictly to the right of mid.

Example:

[4, 5, 6, 7, 0, 1, 2]
 ↑        ↑        ↑
left     mid      right

nums[mid]   = 7
nums[right] = 2

7 > 2

The drop from the larger sorted part to the smaller sorted part must occur somewhere after mid.

Therefore:

left = mid + 1

We can safely exclude mid because nums[mid] > nums[right], so mid cannot be the minimum.

Case 2 — nums[mid] < nums[right]

If:

nums[mid] < nums[right]

then the section from mid to right is sorted:

nums[mid] < ... < nums[right]

Therefore, the minimum cannot be strictly to the right of mid.

However, mid itself may be the minimum.

Example:

[4, 5, 6, 7, 0, 1, 2]
             ↑     ↑
            mid   right

nums[mid]   = 0
nums[right] = 2

Here:

0 < 2

and mid itself is exactly the minimum.

Therefore:

right = mid

Notice that we do not use:

right = mid - 1

because doing so could accidentally remove the answer.

The rightmost element gives us a convenient way to determine which sorted section mid belongs to.

For a rotated array:

[4, 5, 6, 7, 0, 1, 2]

we can think of the values as:

larger section        smaller section
4  5  6  7            0  1  2
                          ↑
                       minimum

Since nums[right] belongs to the smaller section:

nums[mid] > nums[right]

means mid is still in the larger section, so we need to move right.

nums[mid] < nums[right]

means mid is in the smaller section, so the minimum is at mid or somewhere to its left.

We use:

while left < right:

instead of:

while left <= right:

because our search interval always contains the minimum.

We continuously shrink:

[left, right]

until:

left == right

At that point, only one candidate remains.

Therefore:

return nums[left]

Consider:

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

Initially:

left = 0
right = 6

[4, 5, 6, 7, 0, 1, 2]
 ↑        ↑        ↑
 L       mid       R

We have:

nums[mid]   = 7
nums[right] = 2

7 > 2

Therefore:

left = mid + 1

Now:

left = 4
right = 6

[4, 5, 6, 7, 0, 1, 2]
             ↑  ↑  ↑
             L mid R

Now:

nums[mid]   = 1
nums[right] = 2

1 < 2

Therefore:

right = mid

Now:

left = 4
right = 5

[4, 5, 6, 7, 0, 1, 2]
             ↑  ↑
             L  R

Calculate:

mid = 4

So:

nums[mid]   = 0
nums[right] = 1

0 < 1

Therefore:

right = mid

Now:

left = 4
right = 4

So:

left == right

and:

return nums[left]

Result:

0

For example:

[1, 2, 3, 4, 5]

The same algorithm still works.

Initially:

nums[mid]   = 3
nums[right] = 5

3 < 5

So:

right = mid

We continue searching toward the left until:

left == right == 0

and return:

1

No special case is required.

left = 0
right = n - 1

        ↓

while left < right

        ↓

mid = (left + right) // 2

        ↓

Compare nums[mid] with nums[right]

        ↓

┌─────────────────────────┐
│                         │
↓                         ↓

nums[mid] > nums[right]   nums[mid] < nums[right]

minimum is strictly       minimum is at mid
to the right              or to the left

↓                         ↓

left = mid + 1            right = mid

          \               /
           \             /
            ↓           ↓

           left == right

                 ↓

         return nums[left]

This is the most important detail of this problem.

When nums[mid] > nums[right]

mid definitely cannot be the minimum:

nums[mid] > nums[right]

There is already a smaller value at right.

Therefore:

left = mid + 1

When nums[mid] < nums[right]

mid could be the minimum.

Therefore, we must keep mid:

right = mid

not:

right = mid - 1

Time Complexity

Binary Search halves the search interval each time:

O(log n)

Space Complexity

Only a few variables are used:

O(1)

For LeetCode 153, remember:

Compare nums[mid] with nums[right]

Then:

nums[mid] > nums[right]
        ↓
minimum is strictly on the right
        ↓
left = mid + 1

Otherwise:

nums[mid] < nums[right]
        ↓
mid may be the minimum
        ↓
right = mid

Finally:

left == right

and:

return nums[left]

A compact way to remember the entire problem:

mid > right → go right → left = mid + 1

mid < right → keep mid  → right = mid

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 9, 2026

Python solution

class Solution:
    def findMin(self, nums: List[int]) -> int:
        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]

---

Back to Bonus Array · All Algorithm notes