Search in Rotated Sorted Array in DSA Rust - Execution Trace

Concept Flow - Search in Rotated Sorted Array

Start

↓

Set low=0, high=n-1

↓

While low <= high

↓

Calculate mid=(low+high)/2

↓

Check if nums[mid

↓

Return mid

↓

Check which half is sorted

↓

If left half sorted

↓

Check if target in left half

↓

high = mid - 1

↓

low = mid + 1

↓

Else right half sorted

↓

Check if target in right half

↓

low = mid + 1

↓

high = mid - 1

↓

If not found return -1

This flow shows how the search narrows down by checking which half is sorted and adjusting low and high pointers accordingly.

Execution Sample

DSA Rust

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

This code searches for a target in a rotated sorted array using a modified binary search.

Execution Table

Step	Operation	low	high	mid	nums[mid]	Check	Pointer Changes	Visual State
1	Initialize pointers	0	6	-	-	-	low=0, high=6	[4,5,6,7,0,1,2]
2	Calculate mid	0	6	3	7	nums[low]=4 <= nums[mid]=7 (left half sorted)	none	[4,5,6,7,0,1,2]
3	Check target=0 in left half [4..7)?	0	6	3	7	No	low = mid + 1 = 4	[4,5,6,7,0,1,2]
4	Calculate mid	4	6	5	1	nums[low]=0 <= nums[mid]=1 (left half sorted)	none	[4,5,6,7,0,1,2]
5	Check target=0 in left half [0..1)?	4	6	5	1	Yes	high = mid - 1 = 4	[4,5,6,7,0,1,2]
6	Calculate mid	4	4	4	0	nums[mid] == target	Return mid=4	[4,5,6,7,0,1,2]
7	Exit	4	4	4	0	Found target at index 4	Stop	[4,5,6,7,0,1,2]

💡 Target found at index 4, search ends.

Variable Tracker

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

Key Moments - 3 Insights

Why do we check if the left half is sorted using nums[low] <= nums[mid]?

Because in a rotated sorted array, one half is always sorted. Checking nums[low] <= nums[mid] tells us if the left half is sorted. This is shown in execution_table rows 2 and 4.

Why do we adjust low or high based on whether the target lies within the sorted half?

We narrow the search to the half where the target can exist. If target is in the sorted half, we move high or low to mid-1 or mid+1 accordingly. This is seen in rows 3 and 5.

What happens if the target is not found in the array?

The while loop ends when low > high, and the function returns -1. This is the exit condition after all steps if no match is found.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of mid at Step 4?

A 3

B 4

C 5

D 6

💡 Hint

Refer to the 'mid' column in execution_table row with Step 4.

At which step does the algorithm find the target?

A Step 6

B Step 5

C Step 3

D Step 7

💡 Hint

Check the 'Check' column for 'nums[mid] == target' in execution_table.

If the target was 3 instead of 0, what would happen to the pointer changes at Step 3?

A low and high remain unchanged

B low would become mid + 1

C high would become mid - 1

D Search ends immediately

💡 Hint

Look at how pointer changes depend on target position relative to sorted half in execution_table Step 3.

Concept Snapshot

Search in Rotated Sorted Array:
- Use binary search with low, high pointers
- Calculate mid = (low + high) / 2
- Check if nums[mid] == target
- Determine which half is sorted (left or right)
- Narrow search to half containing target
- Repeat until found or low > high
- Return index or -1 if not found

Full Transcript

This concept shows how to search a target in a rotated sorted array using a modified binary search. We start with low and high pointers at the array ends. Each step calculates mid and checks if nums[mid] equals the target. If not, we check which half of the array is sorted by comparing nums[low] and nums[mid]. Depending on where the target lies, we adjust low or high to narrow the search. This repeats until the target is found or the search space is empty. The execution table traces each step with pointer values and decisions. Key moments clarify why we check sorted halves and how pointer adjustments work. The visual quiz tests understanding of mid calculation, target finding step, and pointer changes if target differs.

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