Find Minimum in Rotated Sorted Array in DSA Python - Execution Trace

Concept Flow - Find Minimum in Rotated Sorted Array

Start

↓

Set left=0, right=n-1

↓

Check if array[left

↓

Return array[left

↓

Compare array[mid

↓

mid

↓

left = mid + 1

↓

Repeat until left == right

↓

Return array[left

We use two pointers to narrow down the search space by comparing middle and right elements until we find the smallest element.

Execution Sample

DSA Python

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

This code finds the minimum element in a rotated sorted array using binary search.

Execution Table

Step	Operation	left	right	mid	Compare nums[mid] and nums[right]	Pointer Changes	Array State
1	Initialize pointers	0	6	-	-	left=0, right=6	[4,5,6,7,0,1,2]
2	Check if nums[left] < nums[right]	0	6	-	4 < 2? False	No change	[4,5,6,7,0,1,2]
3	Calculate mid	0	6	3	-	-	[4,5,6,7,0,1,2]
4	Compare nums[mid] and nums[right]	0	6	3	7 > 2? True	left = mid + 1 = 4	[4,5,6,7,0,1,2]
5	Calculate mid	4	6	5	-	-	[4,5,6,7,0,1,2]
6	Compare nums[mid] and nums[right]	4	6	5	1 > 2? False	right = mid = 5	[4,5,6,7,0,1,2]
7	Calculate mid	4	5	4	-	-	[4,5,6,7,0,1,2]
8	Compare nums[mid] and nums[right]	4	5	4	0 > 1? False	right = mid = 4	[4,5,6,7,0,1,2]
9	left == right	4	4	-	-	-	[4,5,6,7,0,1,2]
10	Return minimum	4	4	-	-	-	Minimum is nums[4] = 0

💡 left equals right at index 4, minimum element found at nums[4]

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	Final
left	0	4	4	4	4
right	6	6	5	4	4
mid	-	3	5	4	-

Key Moments - 3 Insights

Why do we compare nums[mid] with nums[right] instead of nums[left]?

Comparing nums[mid] with nums[right] helps decide which side is unsorted and contains the minimum. See steps 4, 6, and 8 in execution_table where this comparison guides pointer moves.

Why do we set right = mid instead of right = mid - 1 when nums[mid] <= nums[right]?

Because nums[mid] could be the minimum, we keep it by setting right = mid. This is shown in steps 6 and 8 where right moves to mid, not mid - 1.

What happens if the array is not rotated?

At step 2, nums[left] < nums[right] is True, so we return nums[left] immediately as the minimum without further searching.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'left' after step 4?

A 0

B 3

C 4

D 6

💡 Hint

Check the 'Pointer Changes' column at step 4 in execution_table.

At which step does the condition 'left == right' become true?

A Step 9

B Step 8

C Step 10

D Step 7

💡 Hint

Look at the 'left' and 'right' columns in execution_table and find when they are equal.

If the array was not rotated and sorted ascending, what would happen at step 2?

A right pointer moves to mid

B The function returns nums[left] immediately

C left pointer moves to mid + 1

D The loop continues without change

💡 Hint

Refer to the 'Compare nums[left] < nums[right]?' condition at step 2 in execution_table.

Concept Snapshot

Find Minimum in Rotated Sorted Array:
- Use two pointers: left=0, right=n-1
- If nums[left] < nums[right], return nums[left]
- Else, find mid = (left+right)//2
- If nums[mid] > nums[right], left = mid + 1
- Else, right = mid
- Repeat until left == right
- Return nums[left] as minimum

Full Transcript

This concept finds the smallest number in a rotated sorted array using a binary search approach. We start with two pointers at the ends of the array. If the left value is less than the right, the array is not rotated, so the left value is the minimum. Otherwise, we calculate the middle index and compare the middle value with the right value. If the middle value is greater, the minimum is in the right half, so we move the left pointer to mid + 1. If not, the minimum is in the left half or at mid, so we move the right pointer to mid. We repeat this until left and right pointers meet. The value at this position is the minimum. The execution table shows each step with pointer updates and comparisons, helping visualize how the search space shrinks until the minimum is found.

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