Find Minimum in Rotated Sorted Array in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the minimum element output in a rotated sorted array

What is the output of the following code that finds the minimum element in a rotated sorted array?

DSA Python

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]

print(find_min([4,5,6,7,0,1,2]))

A 1

B 0

C 4

D 7

💡 Hint

Think about how the binary search narrows down the smallest element by comparing middle and right values.

The code uses binary search to find the smallest element in a rotated sorted array. It compares the middle element with the rightmost element to decide which half to search next. The minimum is 0 in the given array.

❓ Predict Output

intermediate

Output of minimum finder on a non-rotated sorted array

What will the output be when the minimum finder function is run on a sorted array that is not rotated?

DSA Python

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]

print(find_min([1,2,3,4,5,6,7]))

A 3

B 7

C 1

D 4

💡 Hint

If the array is not rotated, the smallest element is the first element.

Since the array is sorted and not rotated, the smallest element is the first element, which is 1.

🔧 Debug

advanced

Identify the error in this minimum finder code

What error will this code produce when trying to find the minimum in a rotated sorted array?

DSA Python

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 - 1
    return nums[left]

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

A Infinite loop

B Returns 1 correctly

C TypeError

D IndexError

💡 Hint

Check the loop condition and how left and right pointers move.

The loop condition 'left <= right' combined with 'right = mid - 1' can cause left to go out of range, leading to IndexError when accessing nums[left].

❓ Predict Output

advanced

Output of minimum finder on array with duplicates

What is the output of the following code when the rotated sorted array contains duplicates?

DSA Python

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
        elif nums[mid] < nums[right]:
            right = mid
        else:
            right -= 1
    return nums[left]

print(find_min([2,2,2,0,1,2]))

A 0

B 1

C 2

D IndexError

💡 Hint

Duplicates require extra handling by reducing right pointer when equal.

The code handles duplicates by decreasing right when nums[mid] equals nums[right], ensuring the minimum 0 is found.

🧠 Conceptual

expert

Why binary search works for finding minimum in rotated sorted array

Why does binary search correctly find the minimum element in a rotated sorted array?

A Because the array is partially sorted and comparing middle with right helps discard half the search space

B Because the array is fully sorted and binary search always works on sorted arrays

C Because the minimum element is always at the middle index after rotation

D Because the array elements are unique and increasing

💡 Hint

Think about how rotation affects sorting and how comparisons guide the search.

Binary search works because the rotated array is made of two sorted parts. Comparing middle and right elements helps decide which part contains the minimum, allowing discarding half the array each step.

Practice

1. What is the main goal when finding the minimum in a rotated sorted array like [4, 5, 6, 7, 0, 1, 2]?

easy

A. To find the smallest number where the rotation happened

B. To find the largest number in the array

C. To sort the array again

D. To count how many times the array was rotated

Solution

1. Step 1: Understand the rotated sorted array

   A rotated sorted array is originally sorted but then shifted. The smallest number is where the rotation happened.

2. Step 2: Identify the minimum element

   The minimum element is the smallest number, marking the rotation point.

3. Final Answer:

   To find the smallest number where the rotation happened -> Option A

4. Quick Check:

   Minimum = smallest number at rotation [OK]

Hint: Minimum is the smallest number where order breaks [OK]

Common Mistakes:

• Looking for the largest number instead
• Trying to sort the array again
• Counting rotations instead of finding minimum

2. Which of the following Python code snippets correctly initializes variables to find the minimum in a rotated sorted array nums using binary search?

easy

A. start, end = len(nums), 0

B. start = 1; end = len(nums)

C. start, end = 0, len(nums) - 1

D. start = -1; end = len(nums) + 1

Solution

1. Step 1: Understand binary search initialization

   Binary search uses start at 0 and end at last index (length - 1).

2. Step 2: Check each option

   start, end = 0, len(nums) - 1 correctly sets start=0 and end=len(nums)-1. Others have invalid ranges.

3. Final Answer:

   start, end = 0, len(nums) - 1 -> Option C

4. Quick Check:

   Binary search range = start=0, end=length-1 [OK]

Hint: Start at 0, end at last index for binary search [OK]

Common Mistakes:

• Setting start or end outside valid index range
• Using length instead of length - 1 for end
• Starting from 1 instead of 0

3. What will be the output of the following code snippet?

def find_min(nums):
    start, end = 0, len(nums) - 1
    while start < end:
        mid = (start + end) // 2
        if nums[mid] > nums[end]:
            start = mid + 1
        else:
            end = mid
    return nums[start]

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

medium

A. 2

B. 3

C. 5

D. 1

Solution

1. Step 1: Trace the binary search steps

   Initial array: [3,4,5,1,2], start=0, end=4 - mid=2, nums[mid]=5, nums[end]=2, 5>2 so start=mid+1=3 - now start=3, end=4 - mid=3, nums[mid]=1, nums[end]=2, 1<=2 so end=mid=3 - start=3, end=3, loop ends

2. Step 2: Return minimum element

   nums[start]=nums[3]=1 is the minimum.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Minimum found = 1 [OK]

Hint: Compare mid and end to adjust search [OK]

Common Mistakes:

• Returning nums[mid] instead of nums[start]
• Not updating start or end correctly
• Confusing > and < in condition

4. The following code is intended to find the minimum in a rotated sorted array, but it has a bug. What is the bug?

def find_min(nums):
    start, end = 0, len(nums) - 1
    while start <= end:
        mid = (start + end) // 2
        if nums[mid] > nums[end]:
            start = mid + 1
        else:
            end = mid
    return nums[start]

medium

A. The loop condition should be start < end, not start <= end

B. The return statement should be nums[end], not nums[start]

C. The mid calculation is incorrect

D. The if condition should compare nums[mid] with nums[start]

Solution

1. Step 1: Analyze the loop condition

   The loop uses start <= end, which can cause infinite loop or index errors because start can pass end.

2. Step 2: Correct loop condition for binary search

   Using start < end ensures the loop stops when start meets end, correctly locating minimum.

3. Final Answer:

   The loop condition should be start < end, not start <= end -> Option A

4. Quick Check:

   Loop condition must be start < end [OK]

Hint: Use start < end for binary search loops [OK]

Common Mistakes:

• Using <= causes infinite loops or wrong indexes
• Changing mid calculation unnecessarily
• Comparing with wrong array element

5. Given a rotated sorted array that may contain duplicates, such as [2, 2, 2, 0, 1, 2], which modification to the binary search approach helps correctly find the minimum?

hard

A. Sort the array first before searching

B. When nums[mid] == nums[end], reduce end by 1 to skip duplicate

C. Always move start to mid + 1 when nums[mid] >= nums[end]

D. Return nums[0] directly as minimum

Solution

1. Step 1: Understand duplicates affect comparison

   When nums[mid] equals nums[end], we cannot decide which side minimum is on because duplicates hide order.

2. Step 2: Skip duplicate by reducing end

   Reducing end by 1 removes one duplicate and narrows search without missing minimum.

3. Final Answer:

   When nums[mid] == nums[end], reduce end by 1 to skip duplicate -> Option B

4. Quick Check:

   Handle duplicates by shrinking end [OK]

Hint: If mid equals end, reduce end by 1 to handle duplicates [OK]

Common Mistakes:

• Assuming no duplicates and using normal binary search
• Sorting array first wastes time
• Returning first element without checking