Search in Rotated Sorted Array in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a rotated sorted array?

A rotated sorted array is an array that was originally sorted in ascending order but then rotated (shifted) at some pivot point. For example, [4,5,6,7,0,1,2] is a rotated version of [0,1,2,4,5,6,7].

beginner

Why can't we use simple binary search directly on a rotated sorted array?

Because the array is not fully sorted in ascending order due to rotation, simple binary search might fail. We need to identify which part of the array is sorted to decide where to search next.

intermediate

In the rotated sorted array [6,7,0,1,2,4,5], if the target is 5, which part of the array should we search?

We check the middle element and compare with the target. Since 5 is between 4 and 5, which is the sorted right half, we search in the right half.

beginner

What is the time complexity of searching in a rotated sorted array using modified binary search?

The time complexity is O(log n) because we still halve the search space each step, just like normal binary search.

intermediate

What are the key steps in the modified binary search for a rotated sorted array?

1. Find the middle element.
2. Check if the target equals the middle.
3. Determine which half is sorted.
4. Decide if the target lies in the sorted half.
5. Search in the half where the target can be.
6. Repeat until found or search space is empty.

What is the first step in searching a target in a rotated sorted array?

A Search linearly from start

B Sort the array again

C Check the first element only

D Find the middle element

We start by finding the middle element to decide which half to search next.

If the left half of the array is sorted and the target lies within its range, where should we search next?

A Right half

B Both halves

C Left half

D None, target not found

If the left half is sorted and the target is within its range, we search the left half.

What is the time complexity of the search in a rotated sorted array using binary search?

A O(log n)

B O(n)

C O(n log n)

D O(1)

The search uses a modified binary search, which runs in O(log n) time.

In the array [4,5,6,7,0,1,2], which element is the pivot point where rotation happened?

A 0

B 7

C 4

D 2

The pivot is the smallest element, 0, where rotation happened.

If the middle element equals the target, what should the algorithm do?

A Search left half

B Return the middle index

C Search right half

D Continue searching both halves

If the middle element matches the target, we return its index immediately.

Explain how to search for a target in a rotated sorted array using binary search.

Think about how rotation affects sorting and how to use that to guide search.

Describe why a rotated sorted array requires a modified binary search instead of a normal binary search.

Consider what rotation does to the order of elements.

Practice

1. What is the main challenge when searching for a target in a rotated sorted array compared to a normal sorted array?

easy

A. The array size is unknown

B. The array contains duplicate elements

C. The array is sorted in descending order

D. The array is split into two sorted parts, making direct binary search tricky

Solution

1. Step 1: Understand the array structure

   A rotated sorted array is originally sorted but then rotated at some pivot, splitting it into two sorted parts.

2. Step 2: Impact on search

   This split means a normal binary search can't be applied directly because the order is disrupted at the pivot.

3. Final Answer:

   The array is split into two sorted parts, making direct binary search tricky -> Option D

4. Quick Check:

   Rotated array = two sorted parts [OK]

Hint: Look for the pivot splitting the array into two sorted halves [OK]

Common Mistakes:

• Assuming the array is fully sorted without rotation
• Ignoring the pivot point in the array
• Thinking duplicates cause the main challenge
• Confusing descending order with rotation

2. Which Rust code snippet correctly declares a function signature to search a target in a rotated sorted array?

easy

A. fn search(nums: &[i32], target: i32) -> Option<usize>

B. fn search(nums: Vec<i32>, target: i32) -> usize

C. fn search(nums: &Vec<i32>, target: i32) -> bool

D. fn search(nums: &[i32], target: i32) -> i32

Solution

1. Step 1: Analyze parameter types

   Using a slice &[i32] is efficient and idiomatic for read-only array input in Rust.

2. Step 2: Analyze return type

   Returning Option<usize> allows indicating if the target was found (Some(index)) or not (None).

3. Final Answer:

   fn search(nums: &[i32], target: i32) -> Option<usize> -> Option A

4. Quick Check:

   Slice input + Option return = fn search(nums: &[i32], target: i32) -> Option<usize> [OK]

Hint: Use &[i32] for input and Option<usize> for index result [OK]

Common Mistakes:

• Using Vec<i32> unnecessarily copies data
• Returning usize without Option loses 'not found' info
• Returning bool loses index information
• Returning i32 index can be ambiguous

3. Given the Rust function below, what is the output when searching for target 3?

fn search(nums: &[i32], target: i32) -> Option<usize> {
    let mut left = 0;
    let mut right = nums.len() - 1;
    while left <= right {
        let mid = (left + right) / 2;
        if nums[mid] == target {
            return Some(mid);
        }
        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    None
}

let arr = [4,5,6,7,0,1,2];
println!("{:?}", search(&arr, 3));

medium

A. None

B. Some(2)

C. Some(4)

D. Some(0)

Solution

1. Step 1: Understand the array and target

   The array is [4,5,6,7,0,1,2], target is 3 which is not present in the array.

2. Step 2: Trace the search logic

   The function performs binary search on rotated array but since 3 is missing, the loop ends returning None.

3. Final Answer:

   None -> Option A

4. Quick Check:

   3 not in array = None [OK]

Hint: If target missing, function returns None [OK]

Common Mistakes:

• Assuming target 3 is present and returning wrong index
• Confusing mid calculation causing infinite loop
• Ignoring rotation logic in conditions
• Returning Some with wrong index

4. Identify the bug in the following Rust code for searching a target in a rotated sorted array:

fn search(nums: &[i32], target: i32) -> Option<usize> {
    let mut left = 0;
    let mut right = nums.len() - 1;
    while left < right {
        let mid = (left + right) / 2;
        if nums[mid] == target {
            return Some(mid);
        }
        if nums[left] <= nums[mid] {
            if nums[left] <= target && target < nums[mid] {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            if nums[mid] < target && target <= nums[right] {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    None
}

medium

A. The function should return bool instead of Option<usize>

B. The mid calculation should use floating division

C. The loop condition should be while left <= right, not while left < right

D. The array should be mutable

Solution

1. Step 1: Analyze loop condition

   The loop uses while left < right, which misses checking when left == right, possibly skipping the last element.

2. Step 2: Correct loop condition

   Changing to while left <= right ensures all elements are checked, including when left equals right.

3. Final Answer:

   The loop condition should be while left <= right, not while left < right -> Option C

4. Quick Check:

   Loop must cover all indices [OK]

Hint: Use while left <= right to cover all elements [OK]

Common Mistakes:

• Using < instead of <= causing missed checks
• Trying floating division for mid index
• Changing return type unnecessarily
• Making array mutable without need

5. You have a rotated sorted array with possible duplicates: [2,2,2,3,4,2]. How would you modify the search algorithm to correctly find target 3?

hard

A. Sort the array before searching

B. Add extra checks to skip duplicates when nums[left] == nums[mid] == nums[right]

C. Use linear search instead of binary search

D. Ignore duplicates and apply normal rotated search

Solution

1. Step 1: Understand duplicates impact

   Duplicates can make it unclear which side is sorted because nums[left], nums[mid], nums[right] may be equal.

2. Step 2: Modify algorithm to skip duplicates

   When nums[left] == nums[mid] == nums[right], increment left and decrement right to skip duplicates and continue search.

3. Step 3: Avoid sorting or linear search

   Sorting changes array order; linear search is inefficient. Proper duplicate handling keeps binary search efficient.

4. Final Answer:

   Add extra checks to skip duplicates when nums[left] == nums[mid] == nums[right] -> Option B

5. Quick Check:

   Skip duplicates to maintain binary search [OK]

Hint: Skip duplicates at edges when equal to mid [OK]

Common Mistakes:

• Sorting array losing rotation info
• Using linear search losing efficiency
• Ignoring duplicates causing wrong results
• Assuming duplicates don't affect logic