Binary Search Recursive Approach in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the middle index in the recursive binary search.

DSA Rust

let mid = (low + [1]) / 2;

Drag options to blanks, or click blank then click option'

Alow

B0

Cmid

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Using low twice instead of low and high.

Using mid before it is defined.

The middle index is found by averaging the low and high indices.

2fill in blank

medium

Complete the code to check if the middle element is equal to the target value.

DSA Rust

if arr[mid] [1] target {

Drag options to blanks, or click blank then click option'

A!=

B>

C==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using assignment '=' instead of comparison '=='.

Using wrong comparison operators.

We check if the middle element matches the target to find it.

3fill in blank

hard

Fix the error in the recursive call when the target is less than the middle element.

DSA Rust

return binary_search(arr, low, [1], target);

Drag options to blanks, or click blank then click option'

Alow - 1

Bmid - 1

Chigh + 1

Dmid + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using mid + 1 which searches the wrong half.

Using low - 1 which can cause invalid indices.

If the target is less than the middle element, search the left half by setting high to mid - 1.

4fill in blank

hard

Fill both blanks to correctly handle the recursive call when the target is greater than the middle element.

DSA Rust

return binary_search(arr, [1], [2], target);

Drag options to blanks, or click blank then click option'

Amid + 1

Blow

Chigh

Dmid - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping low and high values.

Using mid - 1 instead of mid + 1 for low.

When the target is greater, search the right half by setting low to mid + 1 and keeping high the same.

5fill in blank

hard

Fill all three blanks to complete the base case that stops recursion when the target is not found.

DSA Rust

if [1] > [2] {
    return [3];
}

Drag options to blanks, or click blank then click option'

Alow

Bhigh

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 which could be a valid index.

Checking if high > low instead of low > high.

The search ends when low is greater than high, meaning the target is not in the array, so return -1.

Practice

1. What is the main idea behind the binary search recursive approach?

easy

A. Divide the search range in half recursively until the target is found or range is empty

B. Check every element one by one until the target is found

C. Sort the array recursively before searching

D. Use a queue to store elements and search iteratively

Solution

1. Step 1: Understand binary search logic

   Binary search works by repeatedly dividing the search range in half to find the target efficiently.

2. Step 2: Recognize recursive approach

   The recursive approach calls the same function on the half where the target might be, until found or range is empty.

3. Final Answer:

   Divide the search range in half recursively until the target is found or range is empty -> Option A

4. Quick Check:

   Binary search recursive = divide and conquer [OK]

Hint: Binary search halves range recursively to find target fast [OK]

Common Mistakes:

• Thinking binary search checks every element
• Confusing recursion with iteration
• Assuming array must be sorted during search

2. Which of the following is the correct Rust function signature for a recursive binary search on a slice of integers?

easy

A. fn binary_search(arr: &[i32], target: i32) -> bool

B. fn binary_search(arr: Vec usize

C. fn binary_search(arr: &[i32], target: i32, low: usize, high: usize) -> Option<usize>

D. fn binary_search(arr: &mut [i32], target: i32) -> i32

Solution

1. Step 1: Identify parameters for recursion

   Recursive binary search needs the array slice, target, and current low and high indices to narrow search.

2. Step 2: Match correct signature

   fn binary_search(arr: &[i32], target: i32, low: usize, high: usize) -> Option<usize> matches this with slice reference, target, low and high indices, and returns Option with found index.

3. Final Answer:

   fn binary_search(arr: &[i32], target: i32, low: usize, high: usize) -> Option<usize> -> Option C

4. Quick Check:

   Recursive binary search needs low and high indices [OK]

Hint: Recursive binary search needs low and high indices parameters [OK]

Common Mistakes:

• Using Vec instead of slice reference
• Missing low and high parameters for recursion
• Returning wrong type like bool or i32

3. What will be the output of the following Rust code snippet?

fn binary_search(arr: &[i32], target: i32, low: usize, high: usize) -> Option<usize> {
    if low > high {
        return None;
    }
    let mid = low + (high - low) / 2;
    if arr[mid] == target {
        return Some(mid);
    } else if arr[mid] > target {
        return binary_search(arr, target, low, mid - 1);
    } else {
        return binary_search(arr, target, mid + 1, high);
    }
}

fn main() {
    let arr = [2, 4, 6, 8, 10];
    let result = binary_search(&arr, 6, 0, arr.len() - 1);
    println!("{:?}", result);
}

medium

A. Some(3)

B. Some(2)

C. None

D. Some(1)

Solution

1. Step 1: Trace initial call and mid calculation

   Initial call: low=0, high=4, mid=2. arr[2] = 6 matches target 6.

2. Step 2: Return index wrapped in Some

   Since arr[mid] == target, function returns Some(2) immediately.

3. Final Answer:

   Some(2) -> Option B

4. Quick Check:

   Target found at index 2 [OK]

Hint: Calculate mid index and compare target to find result fast [OK]

Common Mistakes:

• Miscomputing mid index
• Confusing index with value
• Forgetting zero-based indexing

4. Identify the error in this recursive binary search Rust function:

fn binary_search(arr: &[i32], target: i32, low: usize, high: usize) -> Option<usize> {
    if low >= high {
        return None;
    }
    let mid = low + (high - low) / 2;
    if arr[mid] == target {
        return Some(mid);
    } else if arr[mid] > target {
        return binary_search(arr, target, low, mid - 1);
    } else {
        return binary_search(arr, target, mid + 1, high);
    }
}

medium

A. The recursive calls should swap low and high parameters

B. Mid calculation should use low + (high - low) / 2 to avoid overflow

C. The function should return usize instead of Option<usize>

D. The base case condition should be low > high, not low >= high

Solution

1. Step 1: Analyze base case condition

   Base case currently returns None if low >= high, but when low == high, the element at that index should still be checked.

2. Step 2: Correct base case to low > high

   Changing condition to low > high ensures the last element is checked before returning None.

3. Final Answer:

   The base case condition should be low > high, not low >= high -> Option D

4. Quick Check:

   Base case must allow low == high check [OK]

Hint: Base case must allow checking when low equals high [OK]

Common Mistakes:

• Stopping search too early by wrong base case
• Ignoring possibility of single element left
• Misusing mid calculation causing overflow

5. Given a sorted array with possible duplicate elements, how can you modify the recursive binary search to find the first occurrence of a target value?

hard

A. When target is found, continue searching left half recursively to find earlier occurrence

B. Return immediately when target is found without further search

C. Use iterative binary search instead of recursive

D. Sort the array again before searching

Solution

1. Step 1: Understand duplicates and first occurrence

   Duplicates mean target may appear multiple times; first occurrence is the smallest index with target.

2. Step 2: Modify recursion to search left half after finding target

   When target is found at mid, recursively search left half to check for earlier occurrence, else return mid.

3. Final Answer:

   When target is found, continue searching left half recursively to find earlier occurrence -> Option A

4. Quick Check:

   Find first occurrence by searching left after match [OK]

Hint: After finding target, search left half to find first occurrence [OK]

Common Mistakes:

• Stopping at first found index ignoring duplicates
• Sorting array again unnecessarily
• Switching to iterative without reason