Find Minimum in Rotated Sorted Array in DSA Python - Build from Scratch

Find Minimum in Rotated Sorted Array

📖 Scenario: You have a list of numbers that was originally sorted from smallest to largest. Then, it was rotated at some unknown point. Your task is to find the smallest number in this rotated list.Think of it like a circular queue of numbers where the smallest number is the 'start' after rotation.

🎯 Goal: Build a program that finds the minimum number in a rotated sorted array using a simple loop.

📋 What You'll Learn

Create a list called rotated_nums with the exact values [4, 5, 6, 7, 0, 1, 2].

Create a variable called min_num and set it to the first element of rotated_nums.

Use a for loop with variable num to go through each element in rotated_nums.

Inside the loop, update min_num if num is smaller than min_num.

Print the value of min_num.

💡 Why This Matters

🌍 Real World

Finding the minimum in a rotated sorted array is useful in systems where data is stored in circular buffers or rotated logs.

💼 Career

This concept helps in technical interviews and understanding how to work with rotated or shifted data efficiently.

1

Create the rotated sorted list

Create a list called rotated_nums with these exact values: [4, 5, 6, 7, 0, 1, 2].

DSA Python

# Create the list rotated_nums with the given values
# Your code here

Hint

Use square brackets [] to create the list and separate numbers with commas.

2

Set the initial minimum number

Create a variable called min_num and set it to the first element of rotated_nums using rotated_nums[0].

DSA Python

rotated_nums = [4, 5, 6, 7, 0, 1, 2]
# Set min_num to the first element of rotated_nums
# Your code here

Hint

Use the index 0 to get the first item from the list.

3

Find the minimum number using a loop

Use a for loop with variable num to go through each element in rotated_nums. Inside the loop, if num is smaller than min_num, update min_num to num.

DSA Python

rotated_nums = [4, 5, 6, 7, 0, 1, 2]
min_num = rotated_nums[0]
# Loop through rotated_nums to find the smallest number
# Your code here

Hint

Use an if statement inside the loop to compare and update min_num.

4

Print the minimum number

Print the value of min_num using print(min_num).

DSA Python

rotated_nums = [4, 5, 6, 7, 0, 1, 2]
min_num = rotated_nums[0]
for num in rotated_nums:
    if num < min_num:
        min_num = num
# Print the minimum number
# Your code here

Hint

Use the print() function to show the result.

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