Binary Search Recursive Approach in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Binary Search Call

What is the output of the following Rust code that performs a recursive binary search on a sorted array?

DSA Rust

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

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

A 4

B -1

C 5

D 3

💡 Hint

Remember that array indices start at 0 and the function returns the index of the target if found.

The target 10 is at index 4 in the array [2, 4, 6, 8, 10, 12]. The recursive binary search returns this index.

❓ Predict Output

intermediate

Result of Recursive Binary Search for Missing Element

What will be printed when searching for a value not present in the array using this recursive binary search?

DSA Rust

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

fn main() {
    let arr = [1, 3, 5, 7, 9];
    let result = binary_search(&arr, 4, 0, arr.len() - 1);
    println!("{}", result);
}

A 4

B 1

C 0

D -1

💡 Hint

If the target is not found, the function returns -1.

Since 4 is not in the array, the function returns -1 indicating the target is missing.

🔧 Debug

advanced

Identify the Runtime Error in Recursive Binary Search

This Rust code for recursive binary search sometimes causes a runtime error. What is the cause?

DSA Rust

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

fn main() {
    let arr = [1, 2, 3, 4, 5];
    let result = binary_search(&arr, 1, 0, arr.len() - 1);
    println!("{}", result);
}

A Index out of bounds when mid is greater than array length

B Overflow when low + high exceeds usize max

C Underflow when mid is 0 and mid - 1 is computed

D Stack overflow due to infinite recursion

💡 Hint

Check what happens when mid is zero and you subtract one.

When mid is 0, mid - 1 causes underflow because usize cannot be negative, leading to a large number and out-of-bounds access.

🧠 Conceptual

advanced

Why Use mid = low + (high - low) / 2 in Binary Search?

In recursive binary search, why is the middle index calculated as mid = low + (high - low) / 2 instead of mid = (low + high) / 2?

A To prevent integer overflow when low and high are large

B To make the code shorter and easier to read

C Because (low + high) / 2 is not a valid expression in Rust

D To ensure mid is always rounded up

💡 Hint

Think about what happens if low and high are very large numbers.

Adding low and high directly can overflow the integer limit, but subtracting first avoids this problem.

❓ Predict Output

expert

Output of Recursive Binary Search with Duplicate Elements

What is the output of this recursive binary search when searching for 3 in an array with duplicates?

DSA Rust

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

fn main() {
    let arr = [1, 2, 3, 3, 3, 4, 5];
    let result = binary_search(&arr, 3, 0, arr.len() - 1);
    println!("{}", result);
}

A 2

B 3

C 4

D -1

💡 Hint

The function returns the first found index of the target, which depends on mid calculation.

The mid calculation leads to index 3 being found first, which contains 3.

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