Search in Rotated Sorted Array in DSA Rust

Mental Model

We want to find a number in a list that was sorted but then rotated. We use a smart search that checks parts of the list to skip unnecessary checks.

Analogy: Imagine a clock face with numbers 1 to 12 in order, but someone turned the clock so 3 is at the top. To find a number, you check which side is still in order and decide where to look next.

Original sorted array:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Rotated array:
4 -> 5 -> 6 -> 7 -> 1 -> 2 -> 3 -> null
Search pointer example:
[low->4] -> 5 -> 6 -> [mid->7] -> 1 -> 2 -> [high->3] -> null

Dry Run Walkthrough

Input: array: [4,5,6,7,0,1,2], target: 0

Goal: Find the index of target 0 in the rotated sorted array

Step 1: Set low=0, high=6, calculate mid=(0+6)/2=3

[low->4] -> 5 -> 6 -> [mid->7] -> 0 -> 1 -> 2 -> [high->2]

Why: We start searching in the whole array by checking the middle element

Step 2: Check if mid element 7 equals target 0 (no), then check which half is sorted

[low->4] -> 5 -> 6 -> [mid->7] -> 0 -> 1 -> 2 -> [high->2]

Why: We need to know which side is sorted to decide where to search next

Step 3: Left half 4 to 7 is sorted, target 0 is not in [4..7], so move low to mid+1=4

4 -> 5 -> 6 -> 7 -> [low->0] -> 1 -> 2 -> [high->2]

Why: Since target is not in sorted left half, search right half

Step 4: Calculate mid=(4+6)/2=5, mid element is 1

4 -> 5 -> 6 -> 7 -> [low->0] -> [mid->1] -> 2 -> [high->2]

Why: Narrow down search to right half

Step 5: Check if mid element 1 equals target 0 (no), check which half is sorted

4 -> 5 -> 6 -> 7 -> [low->0] -> [mid->1] -> 2 -> [high->2]

Why: Decide next search half based on sorted side

Step 6: Right half 1 to 2 is sorted, target 0 is not in [1..2], so move high to mid-1=4

4 -> 5 -> 6 -> 7 -> [low->0] -> [high->0] -> 2 -> null

Why: Target must be in left half now

Step 7: Calculate mid=(4+4)/2=4, mid element is 0

4 -> 5 -> 6 -> 7 -> [mid->0] -> null

Why: Check the last possible position

Step 8: Mid element equals target 0, return index 4

4 -> 5 -> 6 -> 7 -> [found->0] -> null

Why: Target found, stop searching

Result:

4 -> 5 -> 6 -> 7 -> [found->0] -> 1 -> 2 -> null
Answer: index 4

Annotated Code

DSA Rust

fn search_rotated_array(nums: &[i32], target: i32) -> i32 {
    let mut low = 0;
    let mut high = nums.len() as i32 - 1;
    while low <= high {
        let mid = low + (high - low) / 2;
        if nums[mid as usize] == target {
            return mid;
        }
        // Check if left half is sorted
        if nums[low as usize] <= nums[mid as usize] {
            // Target in left half?
            if nums[low as usize] <= target && target < nums[mid as usize] {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else {
            // Right half is sorted
            if nums[mid as usize] < target && target <= nums[high as usize] {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    -1
}

fn main() {
    let nums = vec![4,5,6,7,0,1,2];
    let target = 0;
    let index = search_rotated_array(&nums, target);
    if index != -1 {
        println!("{} found at index {}", target, index);
    } else {
        println!("{} not found", target);
    }
}

while low <= high {

loop until search space is empty

let mid = low + (high - low) / 2;

calculate middle index to check

if nums[mid as usize] == target { return mid; }

if middle element is target, return index

if nums[low as usize] <= nums[mid as usize] {

check if left half is sorted

if nums[low as usize] <= target && target < nums[mid as usize] { high = mid - 1; } else { low = mid + 1; }

decide if target is in left half or right half

else { if nums[mid as usize] < target && target <= nums[high as usize] { low = mid + 1; } else { high = mid - 1; } }

if left half not sorted, right half must be sorted; decide target side

Output

0 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space by checking sorted halves

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), this binary search approach is much faster on large arrays

Edge Cases

empty array

returns -1 immediately because low > high

DSA Rust

while low <= high {

array with one element matching target

returns index 0 immediately

DSA Rust

if nums[mid as usize] == target { return mid; }

array with one element not matching target

returns -1 after one check

DSA Rust

while low <= high {

When to Use This Pattern

When you see a sorted array that has been rotated and need to search quickly, use this pattern to apply modified binary search by checking which half is sorted.

Common Mistakes

Mistake: Not checking which half is sorted before deciding where to search next
Fix: Always check if left half is sorted or else right half is sorted, then decide target side accordingly

Mistake: Using normal binary search without rotation logic, causing wrong results
Fix: Incorporate rotation checks to handle the shifted sorted array

Summary

Finds target index in a rotated sorted array using modified binary search.

Use when searching in arrays that were sorted but then rotated at some pivot.

Key insight: one half of the array is always sorted, use that to decide search direction.

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