Problem Description

You are given an array that was originally sorted in ascending order, but has been rotated between 1 and n times (where n is the length of the array).

A rotation means taking the last element and moving it to the front. For example:

• Original array: [0,1,2,4,5,6,7]
• After 1 rotation: [7,0,1,2,4,5,6]
• After 4 rotations: [4,5,6,7,0,1,2]
• After 7 rotations: [0,1,2,4,5,6,7] (back to original)

Your task is to find and return the minimum element in this rotated sorted array.

Key requirements:

• All elements in the array are unique (no duplicates)
• Your algorithm must run in O(log n) time complexity

The solution uses binary search to efficiently find the minimum element. The key insight is that in a rotated sorted array, the minimum element is at the "pivot point" where the rotation occurred. The algorithm compares elements with nums[0] to determine which half of the array contains the pivot point:

• If nums[0] <= nums[-1], the array is not rotated (or rotated n times), so the minimum is nums[0]
• Otherwise, use binary search to find where the rotation break occurs by checking if nums[mid] is greater than or equal to nums[0] to decide which half to search next

Intuition

When we look at a rotated sorted array, we can observe a key pattern: the array can be divided into two sorted portions. For example, in [4,5,6,7,0,1,2], we have [4,5,6,7] and [0,1,2] - both sorted, but there's a "break" between them where the values drop from 7 to 0.

The minimum element will always be at this break point - specifically, it's the first element of the second sorted portion.

Since we need O(log n) time complexity, we can't scan through the entire array. This constraint immediately suggests binary search.

The challenge is: how do we know which half to search? Here's the key insight - we can use the first element nums[0] as a reference point:

1. If the array hasn't been rotated (or rotated exactly n times), then nums[0] <= nums[-1], and nums[0] is already the minimum.

2. If the array is rotated, then nums[0] belongs to the "upper" sorted portion (the larger values). Any element in this upper portion will be >= nums[0], while elements in the "lower" sorted portion will be < nums[0].

3. During binary search, when we look at nums[mid]:

   • If nums[mid] >= nums[0], then mid is in the upper portion, so the minimum must be to the right (set left = mid + 1)
   • If nums[mid] < nums[0], then mid is in the lower portion where the minimum exists, but mid itself could be the minimum (set right = mid)

This way, we progressively narrow down to the exact point where the rotation break occurs, which is where our minimum element resides.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Check if the array is rotated

if nums[0] <= nums[-1]:
    return nums[0]

First, we check if the first element is less than or equal to the last element. If true, the array hasn't been rotated (or has been rotated exactly n times back to its original position), so the minimum is simply nums[0].

Step 2: Initialize binary search pointers

left, right = 0, len(nums) - 1

We set up two pointers for binary search - left starting at index 0 and right at the last index.

Step 3: Binary search loop

while left < right:
    mid = (left + right) >> 1

We continue searching while left < right. The middle index is calculated using bit shift operation >> 1 (equivalent to dividing by 2), which is slightly more efficient than (left + right) // 2.

Step 4: Determine which half contains the minimum

if nums[0] <= nums[mid]:
    left = mid + 1
else:
    right = mid

This is the core logic:

• If nums[0] <= nums[mid], it means mid is in the upper sorted portion (before the rotation break). The minimum must be in the right half, so we move left to mid + 1.
• If nums[0] > nums[mid], it means mid is in the lower sorted portion (after the rotation break). The minimum could be at mid itself or to its left, so we set right = mid (not mid - 1 to preserve the potential minimum).

Step 5: Return the result

return nums[left]

When the loop exits (left == right), both pointers converge at the minimum element's position.

Time Complexity: O(log n) - We eliminate half of the search space in each iteration. Space Complexity: O(1) - We only use a constant amount of extra space for the pointers.

Example Walkthrough

Let's trace through the algorithm with the array [4,5,6,7,0,1,2].

Initial Check:

• nums[0] = 4 and nums[-1] = 2
• Since 4 > 2, the array is rotated, so we proceed with binary search

Binary Search Process:

Iteration 1:

• left = 0, right = 6
• mid = (0 + 6) >> 1 = 3
• nums[mid] = nums[3] = 7
• Compare: nums[0] = 4 <= nums[3] = 7 ✓
• This means index 3 is in the upper sorted portion [4,5,6,7]
• The minimum must be to the right of mid
• Update: left = mid + 1 = 4

Iteration 2:

• left = 4, right = 6
• mid = (4 + 6) >> 1 = 5
• nums[mid] = nums[5] = 1
• Compare: nums[0] = 4 <= nums[5] = 1 ✗
• This means index 5 is in the lower sorted portion [0,1,2]
• The minimum could be at mid or to its left
• Update: right = mid = 5

Iteration 3:

• left = 4, right = 5
• mid = (4 + 5) >> 1 = 4
• nums[mid] = nums[4] = 0
• Compare: nums[0] = 4 <= nums[4] = 0 ✗
• Index 4 is in the lower sorted portion
• The minimum could be at mid itself
• Update: right = mid = 4

Termination:

• left = 4, right = 4 (converged)
• Return nums[4] = 0

The algorithm correctly identifies that the minimum element 0 is at index 4, which is exactly where the rotation break occurs (between 7 and 0).

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n), where n is the length of the input array nums.

The algorithm uses binary search to find the minimum element in a rotated sorted array. In each iteration of the while loop, the search space is reduced by half. The number of iterations is logarithmic with respect to the array size, as we divide the search range by 2 in each step until left >= right. The initial check if nums[0] <= nums[-1] takes O(1) time, and all operations inside the loop (comparison and index calculations) are O(1). Therefore, the overall time complexity is O(log n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space. It maintains three integer variables (left, right, and mid) regardless of the input size. No additional data structures are created, and the algorithm operates directly on the input array without recursion (which would use stack space). Thus, the space complexity is constant.

Common Pitfalls

1. Incorrect Boundary Update When Moving Right Pointer

The Pitfall: A common mistake is setting right = mid - 1 instead of right = mid when nums[0] > nums[mid]:

# INCORRECT
if nums[0] <= nums[mid]:
    left = mid + 1
else:
    right = mid - 1  # Wrong! Could skip the minimum

Why This Fails: When nums[0] > nums[mid], the element at mid could actually be the minimum itself. By setting right = mid - 1, we might exclude the minimum from our search range.

Example: For array [4,5,1,2,3]:

• mid = 2, nums[mid] = 1
• Since nums[0] = 4 > nums[mid] = 1, we know minimum is in left half
• But nums[mid] = 1 IS the minimum! Setting right = mid - 1 would skip it

Solution: Always use right = mid to preserve the potential minimum:

if nums[0] <= nums[mid]:
    left = mid + 1
else:
    right = mid  # Correct: keeps mid in search range

2. Comparing with Wrong Reference Point

The Pitfall: Using nums[left] instead of nums[0] as the reference for comparison:

# INCORRECT
if nums[left] <= nums[mid]:  # Wrong reference point!
    left = mid + 1
else:
    right = mid

Why This Fails: As left changes during the search, nums[left] no longer represents the start of the rotated array. This breaks the logic for determining which half contains the rotation point.

Example: For array [4,5,6,7,0,1,2]:

• Initially: left = 0, mid = 3, nums[left] = 4 <= nums[mid] = 7 ✓
• After update: left = 4, mid = 5, nums[left] = 0 <= nums[mid] = 1 ✓
• This would incorrectly move left to 6, missing the minimum at index 4

Solution: Always compare with the fixed reference nums[0]:

if nums[0] <= nums[mid]:  # Correct: fixed reference point
    left = mid + 1
else:
    right = mid

3. Forgetting Edge Cases

The Pitfall: Not handling arrays with single element or unrotated arrays:

# INCORRECT - jumps straight to binary search
def findMin(self, nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        # ... binary search logic

Why This Fails:

• Single element arrays would work but are inefficient
• Unrotated arrays would unnecessarily go through binary search when the answer is simply nums[0]

Solution: Add the initial check:

if nums[0] <= nums[-1]:
    return nums[0]

This handles both unrotated arrays and single-element arrays efficiently in O(1) time.