Binary Search Recursive Approach in DSA Rust - Execution Trace

Concept Flow - Binary Search Recursive Approach

Start with full array range

↓

Calculate middle index

↓

Compare middle element with target

↓

Search right half

↓

Search left half

↓

Repeat until range invalid

↓

Return -1 (not found)

The recursive binary search splits the array range by comparing the middle element to the target, then recursively searches the left or right half until the target is found or the range is empty.

Execution Sample

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 {
        return mid as i32;
    } else if arr[mid] < target {
        binary_search(arr, target, mid + 1, high)
    } else {
        binary_search(arr, target, low, mid - 1)
    }
}

This function recursively searches for target in a sorted array by narrowing the search range based on comparisons.

Execution Table

Step	Operation	Current Range (low..high)	Mid Index	Mid Value	Comparison	Next Range	Result / Return
1	Start search	0..6	3	7	7 < 9? Yes	4..6
2	Recurse right half	4..6	5	9	9 == 9? Yes		Return 5
3	End						Found target at index 5

💡 Search ends when target is found at index 5 or range becomes invalid

Variable Tracker

Variable	Start	After Step 1	After Step 2	Final
low	0	4	4	4
high	6	6	6	6
mid		3	5	5
mid_value		7	9	9
result				5

Key Moments - 3 Insights

Why do we check if low > high to stop recursion?

Because when low is greater than high, it means the search range is empty and the target is not in the array. This is shown in execution_table row 1 where if low > high, we return -1.

Why do we calculate mid as (low + high) / 2?

Calculating mid this way finds the middle index of the current search range, splitting the array into two halves. This is shown in execution_table rows 1 and 2 where mid changes as the range narrows.

What happens if the middle element equals the target?

The function returns the mid index immediately, ending recursion. This is shown in execution_table row 2 where mid value 9 equals target 9 and returns index 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is the mid index at Step 1?

A 3

B 5

C 4

D 6

💡 Hint

Check the 'Mid Index' column in execution_table row 1

At which step does the function find the target?

A Step 1

B Step 2

C Step 3

D Never

💡 Hint

Look at the 'Comparison' and 'Result / Return' columns in execution_table row 2

If the target was 5 instead of 9, what would be the next range after Step 1?

A 0..2

B 4..6

C 0..3

D 3..6

💡 Hint

Since mid value 7 is greater than 5, next range is left half: low to mid-1, see execution_table logic

Concept Snapshot

Binary Search Recursive Approach:
- Input: sorted array, target, low index, high index
- Calculate mid = (low + high) / 2
- If arr[mid] == target, return mid
- If arr[mid] < target, search right half (mid+1 to high)
- Else, search left half (low to mid-1)
- Stop when low > high (target not found)

Full Transcript

Binary Search Recursive Approach works by repeatedly dividing the search range in half. We start with the full array range and calculate the middle index. We compare the middle element with the target. If they match, we return the index. If the middle element is less than the target, we search the right half recursively. Otherwise, we search the left half recursively. The recursion stops when the search range becomes invalid (low > high), meaning the target is not in the array. This method efficiently finds the target in a sorted array by cutting the search space in half each step.

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