Binary Search Recursive Approach in DSA Rust

Mental Model

Binary search splits a sorted list in half repeatedly to find a target quickly. It checks the middle and decides which half to search next.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if the word is in the first or second half, and repeating this until you find it.

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Search range: low -> 0, high -> 6
Middle index: mid -> 3 (value 7)

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], target: 9

Goal: Find the index of target 9 using recursive binary search

Step 1: Check middle element at index 3 (value 7)

[1, 3, 5, [7], 9, 11, 13]

Why: Middle helps decide which half to search next

Step 2: Since 9 > 7, search right half: indexes 4 to 6

[9, 11, 13] (indexes 4 to 6)

Why: Target must be in right half because it is greater than middle

Step 3: Check middle element at index 5 (value 11)

[9, [11], 13]

Why: Find new middle in the right half

Step 4: Since 9 < 11, search left half: index 4 to 4

[9] (index 4)

Why: Target must be in left half because it is less than middle

Step 5: Check middle element at index 4 (value 9)

[[9]]

Why: Found the target at index 4

Result:

Final state: [1, 3, 5, 7, [9], 11, 13]
Answer: Target 9 found at index 4

Annotated Code

DSA Rust

fn binary_search_recursive(arr: &[i32], target: i32, low: usize, high: usize) -> Option<usize> {
    if low > high {
        return None; // base case: target not found
    }
    let mid = low + (high - low) / 2; // find middle index
    if arr[mid] == target {
        return Some(mid); // target found
    } else if arr[mid] < target {
        // search right half
        return binary_search_recursive(arr, target, mid + 1, high);
    } else {
        // search left half
        if mid == 0 {
            return None; // prevent underflow
        }
        return binary_search_recursive(arr, target, low, mid - 1);
    }
}

fn main() {
    let arr = [1, 3, 5, 7, 9, 11, 13];
    let target = 9;
    match binary_search_recursive(&arr, target, 0, arr.len() - 1) {
        Some(index) => println!("Target {} found at index {}", target, index),
        None => println!("Target {} not found", target),
    }
}

if low > high { return None; }

base case: stop if search range is invalid

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

calculate middle index to split array

if arr[mid] == target { return Some(mid); }

check if middle element is target

else if arr[mid] < target { return binary_search_recursive(arr, target, mid + 1, high); }

search right half if target is greater

else { if mid == 0 { return None; } return binary_search_recursive(arr, target, low, mid - 1); }

search left half if target is smaller, handle underflow

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range

Space: O(log n) due to recursive call stack depth proportional to log n

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

Edge Cases

empty array

returns None immediately because low > high

DSA Rust

if low > high { return None; }

target not in array

recursion ends when low > high, returns None

DSA Rust

if low > high { return None; }

target is first element

found quickly by recursive checks

DSA Rust

if arr[mid] == target { return Some(mid); }

prevent underflow when mid is 0

returns None instead of wrapping around

DSA Rust

if mid == 0 { return None; }

When to Use This Pattern

When you need to find an item quickly in a sorted list, use recursive binary search because it halves the search space each step.

Common Mistakes

Mistake: Not handling the case when mid is 0 before subtracting 1, causing underflow
Fix: Add a check for mid == 0 before calling recursion on left half

Mistake: Using (low + high) / 2 directly which can overflow
Fix: Use low + (high - low) / 2 to safely calculate mid

Mistake: Not returning the recursive call result, causing no result propagation
Fix: Always return the recursive call's result

Summary

It finds a target in a sorted array by repeatedly checking the middle and searching half the array.

Use it when you have a sorted list and want fast search.

The key is to split the search space in half each time to quickly zero in on the target.

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