Find Minimum in Rotated Sorted Array in DSA Rust

Mental Model

A rotated sorted array is like a sorted list that has been shifted. The smallest element is the point where the order breaks.

Analogy: Imagine a clock face turned clockwise by some hours. The smallest number is where the clock starts again after rotation.

Original sorted array:
[1] -> [2] -> [3] -> [4] -> [5] -> null

Rotated array example:
[4] -> [5] -> [1] -> [2] -> [3] -> null
               ↑ smallest element

Dry Run Walkthrough

Input: array: [4, 5, 1, 2, 3]

Goal: Find the smallest number in the rotated sorted array efficiently

Step 1: Set left=0, right=4 (start and end indices)

array: [4, 5, 1, 2, 3], left=0, right=4

Why: We start searching between the whole array

Step 2: Calculate mid = (0+4)//2 = 2, check array[mid]=1

array: [4, 5, 1, 2, 3], left=0, mid=2, right=4

Why: Mid helps us decide which half contains the smallest element

Step 3: Compare array[mid]=1 with array[right]=3; since 1 < 3, move right to mid=2

array: [4, 5, 1, 2, 3], left=0, right=2

Why: Smallest must be in left half including mid

Step 4: Calculate mid = (0+2)//2 = 1, check array[mid]=5

array: [4, 5, 1, 2, 3], left=0, mid=1, right=2

Why: Narrowing down to find the smallest element

Step 5: Compare array[mid]=5 with array[right]=1; since 5 > 1, move left to mid+1=2

array: [4, 5, 1, 2, 3], left=2, right=2

Why: Smallest must be in right half excluding mid

Step 6: Left equals right at 2, array[left]=1 is the smallest element

array: [4, 5, 1, 2, 3], left=2, right=2, smallest=1

Why: Search ends when left meets right

Result:

array: [4, 5, 1, 2, 3], smallest element = 1

Annotated Code

DSA Rust

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; // smallest is in right half
        } else {
            right = mid; // smallest is in left half including mid
        }
    }
    nums[left]
}

fn main() {
    let nums = vec![4, 5, 1, 2, 3];
    let min_value = find_min(&nums);
    println!("{}", min_value);
}

while left < right {

loop until search space narrows to one element

let mid = left + (right - left) / 2;

find middle index to split search space, avoiding potential overflow

if nums[mid] > nums[right] {

if middle element is greater than right, smallest is in right half

left = mid + 1; // smallest is in right half

move left pointer to mid+1 to discard left half

right = mid; // smallest is in left half including mid

otherwise, move right pointer to mid to keep left half

nums[left]

return the smallest element found

Output

1

Complexity Analysis

Time: O(log n) because the search space halves each iteration

Space: O(1) because only a few variables are used

vs Alternative: Naive approach scans all elements O(n), this binary search method is faster for large arrays

Edge Cases

Array not rotated (e.g., [1, 2, 3, 4, 5])

Algorithm returns the first element as smallest

DSA Rust

while left < right {

Array with one element (e.g., [10])

Returns that single element immediately

DSA Rust

let mut right = nums.len() - 1;

Array rotated at last element (e.g., [2, 3, 4, 5, 1])

Algorithm correctly finds the smallest element at the end

DSA Rust

if nums[mid] > nums[right] {

When to Use This Pattern

When you see a sorted array that might be rotated and need to find the smallest element quickly, use binary search to find the rotation point.

Common Mistakes

Mistake: Using linear search instead of binary search
Fix: Use binary search logic to reduce time complexity from O(n) to O(log n)

Mistake: Incorrectly updating left or right pointers causing infinite loop
Fix: Ensure left moves to mid+1 only when nums[mid] > nums[right], else right moves to mid

Summary

Finds the smallest element in a rotated sorted array using binary search.

Use when you have a sorted array rotated at some pivot and need the minimum efficiently.

The smallest element is the only place where order breaks, found by comparing mid and right elements.

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