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

Concept Flow - Find Minimum in Rotated Sorted Array

Start with full array

↓

Check if array is rotated?

No↓

Return first element

↓

While low < high

↓

Find mid = (low+high)/2

↓

Compare mid element with high element

↓

low = mid+1

↓

Loop until low == high

↓

Return element at low

We check if the array is rotated. If not, the first element is minimum. Otherwise, we use binary search comparing middle and high elements to narrow down the minimum's position until low meets high.

Execution Sample

DSA Rust

fn find_min(nums: &[i32]) -> i32 {
    let mut low = 0;
    let mut high = nums.len() - 1;
    while low < high {
        let mid = (low + high) / 2;
        if nums[mid] > nums[high] {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    nums[low]
}

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

Execution Table

Step	Operation	low	high	mid	nums[mid]	nums[high]	Pointer Changes	Visual State
1	Initialize pointers	0	6	-	-	-	low=0, high=6	[4,5,6,7,0,1,2]
2	Check if rotated	0	6	-	-	-	Array is rotated	[4,5,6,7,0,1,2]
3	Calculate mid	0	6	3	7	2	mid=3	[4,5,6,7,0,1,2]
4	Compare nums[mid] > nums[high]	0	6	3	7	2	7 > 2 is True	[4,5,6,7,0,1,2]
5	Move low to mid+1	4	6	-	-	-	low=4	[4,5,6,7,0,1,2]
6	Calculate mid	4	6	5	1	2	mid=5	[4,5,6,7,0,1,2]
7	Compare nums[mid] > nums[high]	4	6	5	1	2	1 > 2 is False	[4,5,6,7,0,1,2]
8	Move high to mid	4	5	-	-	-	high=5	[4,5,6,7,0,1,2]
9	Calculate mid	4	5	4	0	1	mid=4	[4,5,6,7,0,1,2]
10	Compare nums[mid] > nums[high]	4	5	4	0	1	0 > 1 is False	[4,5,6,7,0,1,2]
11	Move high to mid	4	4	-	-	-	high=4	[4,5,6,7,0,1,2]
12	Check loop condition	4	4	-	-	-	low == high, exit loop	[4,5,6,7,0,1,2]
13	Return minimum	4	4	-	-	-	Return nums[4] = 0	[4,5,6,7,0,1,2]

💡 Loop ends when low equals high, pointing to the minimum element.

Variable Tracker

Variable	Start	After Step 5	After Step 8	After Step 11	Final
low	0	4	4	4	4
high	6	6	5	4	4
mid	-	3	5	4	4
nums[mid]	-	7	1	0	0
nums[high]	-	2	2	0	0

Key Moments - 3 Insights

Why do we compare nums[mid] with nums[high] instead of nums[low]?

Comparing nums[mid] with nums[high] helps decide which side contains the minimum. If nums[mid] > nums[high], minimum is right side, so we move low. Otherwise, minimum is left side or at mid, so we move high. See steps 4 and 7 in execution_table.

Why does the loop stop when low equals high?

When low equals high, it means we have narrowed down to one element, which is the minimum. The loop condition low < high fails, so we exit and return nums[low]. See step 12.

What if the array is not rotated?

If the array is not rotated, nums[low] <= nums[high] at start, so the minimum is the first element. The code still works because the binary search will quickly narrow to low=0. See step 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'low' after step 5?

A 4

B 3

C 5

D 0

💡 Hint

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

At which step does the loop condition low < high become false?

A Step 11

B Step 12

C Step 13

D Step 10

💡 Hint

Look for the step where 'low == high, exit loop' is noted in execution_table.

If nums[mid] was always less than nums[high], which pointer moves?

A low moves up

B both move

C high moves down

D no pointer moves

💡 Hint

Refer to steps 7 and 10 where nums[mid] <= nums[high] causes high to move.

Concept Snapshot

Find Minimum in Rotated Sorted Array:
- Use binary search with low=0, high=n-1
- While low < high:
  - mid = (low + high) / 2
  - If nums[mid] > nums[high], low = mid + 1
  - Else, high = mid
- When loop ends, nums[low] is minimum
- Works because array is sorted and rotated

Full Transcript

This concept finds the smallest number in a rotated sorted array using binary search. We start with two pointers, low and high, at the ends of the array. We check the middle element and compare it with the element at high. If the middle is greater, the minimum is to the right, so we move low up. Otherwise, the minimum is to the left or at mid, so we move high down. We repeat until low meets high. The element at low is the minimum. This method is efficient and works even if the array is not rotated, returning the first element as minimum.

Practice

1. What is the main goal when finding the minimum in a rotated sorted array?

easy

A. To sort the array back to original order

B. To find the smallest element after the rotation point

C. To count how many times the array was rotated

D. To find the largest element in the array

Solution

1. Step 1: Understand the rotated sorted array

   A rotated sorted array is a sorted array shifted some positions, so the smallest element is the rotation point.

2. Step 2: Identify the minimum element

   The minimum element is the smallest value after the rotation point, which is what we want to find.

3. Final Answer:

   To find the smallest element after the rotation point -> Option B

4. Quick Check:

   Minimum element = smallest after rotation [OK]

Hint: Look for the smallest number where order breaks [OK]

Common Mistakes:

• Confusing minimum with maximum element
• Trying to count rotations instead of finding minimum
• Assuming array is fully sorted without rotation

2. Which Rust code snippet correctly declares a function to find the minimum in a rotated sorted array?

easy

A. fn find_min(nums: &[i32]) -> i32 { /* implementation */ }

B. function find_min(nums: Vec<i32>) -> i32 { }

C. def find_min(nums: &[i32]) -> i32 { }

D. fn find_min(nums: Vec<i32>) { return i32; }

Solution

1. Step 1: Check Rust function syntax

   Rust functions start with fn, parameters have types, and return type is after ->.

2. Step 2: Validate each option

   fn find_min(nums: &[i32]) -> i32 { /* implementation */ } uses correct Rust syntax with slice &[i32] and return type i32. Others use wrong keywords or syntax.

3. Final Answer:

   fn find_min(nums: &[i32]) -> i32 { /* implementation */ } -> Option A

4. Quick Check:

   Rust fn syntax with &[i32] and -> i32 [OK]

Hint: Rust functions use fn, param: type, -> return_type [OK]

Common Mistakes:

• Using 'function' keyword instead of 'fn'
• Mixing Python or JavaScript syntax
• Incorrect return type placement

3. What is the output of the following Rust code?

fn main() {
    let nums = vec![4,5,6,7,0,1,2];
    let min = find_min(&nums);
    println!("{}", min);
}

fn find_min(nums: &[i32]) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;
    while left < right {
        let mid = left + (right - left) / 2;
        if nums[mid] > nums[right] {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    nums[left]
}

medium

A. 0

B. 4

C. 7

D. 2

Solution

1. Step 1: Understand the binary search logic

   The code uses binary search to find the smallest element by comparing mid and right elements.

2. Step 2: Trace the loop with input [4,5,6,7,0,1,2]

   Mid moves to find the point where array rotates; finally left points to 0, the smallest element.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Minimum in rotated array = 0 [OK]

Hint: Binary search narrows to smallest element [OK]

Common Mistakes:

• Returning nums[mid] instead of nums[left]
• Confusing left and right pointers
• Not handling rotation correctly

4. Identify the bug in this Rust function to find the minimum in a rotated sorted array:

fn find_min(nums: &[i32]) -> i32 {
    let mut left = 0;
    let mut right = nums.len();
    while left < right {
        let mid = left + (right - left) / 2;
        if nums[mid] > nums[right] {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    nums[left]
}

medium

A. nums[left] should be nums[right] at the end

B. left should start at 1 instead of 0

C. mid calculation causes infinite loop

D. right should be nums.len() - 1 to avoid out-of-bounds

Solution

1. Step 1: Check initialization of right pointer

   right is set to nums.len(), which is out of array bounds (index max is len-1).

2. Step 2: Correct right initialization

   right should be nums.len() - 1 to avoid accessing nums[right] out of bounds.

3. Final Answer:

   right should be nums.len() - 1 to avoid out-of-bounds -> Option D

4. Quick Check:

   Array index max = len-1 [OK]

Hint: Array indices go from 0 to len-1 [OK]

Common Mistakes:

• Using nums.len() as index causes panic
• Starting left at 1 misses first element
• Changing mid calculation unnecessarily

5. Given a rotated sorted array that may contain duplicates, which modification is needed in the binary search to find the minimum correctly?

fn find_min(nums: &[i32]) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;
    while left < right {
        let mid = left + (right - left) / 2;
        if nums[mid] > nums[right] {
            left = mid + 1;
        } else if nums[mid] < nums[right] {
            right = mid;
        } else {
            right -= 1; // What is the reason for this?
        }
    }
    nums[left]
}

hard

A. To avoid infinite loop by always moving left

B. To speed up search by skipping elements

C. To handle duplicates by shrinking right when equal to mid

D. To sort the array during search

Solution

1. Step 1: Understand duplicates effect

   When nums[mid] equals nums[right], we cannot decide which side minimum lies, so we reduce right by one.

2. Step 2: Reason for right -= 1

   This safely shrinks the search space without missing the minimum, handling duplicates correctly.

3. Final Answer:

   To handle duplicates by shrinking right when equal to mid -> Option C

4. Quick Check:

   Duplicates need careful right pointer move [OK]

Hint: When equal, reduce right to handle duplicates [OK]

Common Mistakes:

• Ignoring duplicates causes wrong minimum
• Moving left instead of right when equal
• Assuming no duplicates in rotated array