Binary Search Recursive Approach in DSA Rust - Build from Scratch

Binary Search Recursive Approach

📖 Scenario: You have a sorted list of numbers. You want to find if a certain number is in this list quickly. Binary search helps you do this by checking the middle number and deciding which half to look at next.

🎯 Goal: Build a recursive binary search function in Rust that finds the position of a target number in a sorted list. If the number is not found, it should return -1.

📋 What You'll Learn

Create a sorted list of integers called numbers with these exact values: 2, 4, 6, 8, 10, 12, 14

Create two variables called start and end with values 0 and numbers.len() - 1 respectively

Write a recursive function called binary_search that takes numbers, start, end, and target as parameters and returns the index of target or -1 if not found

Call binary_search with numbers, start, end, and target = 10 and print the result

💡 Why This Matters

🌍 Real World

Binary search is used in many software systems to quickly find data in sorted lists, like searching for a word in a dictionary app or finding a contact in a phone book.

💼 Career

Understanding binary search is fundamental for software developers and engineers because it teaches efficient searching techniques and recursion, which are common in coding interviews and real-world problem solving.

1

Create the sorted list

Create a vector called numbers with these exact integers: 2, 4, 6, 8, 10, 12, 14

DSA Rust

# Create the vector numbers with the given integers
# Your code here

Hint

Use let numbers = vec![2, 4, 6, 8, 10, 12, 14]; to create the vector.

2

Set start and end indices

Create two variables called start and end. Set start to 0 and end to numbers.len() - 1

DSA Rust

fn main() {
    let numbers = vec![2, 4, 6, 8, 10, 12, 14];
    // Create start and end variables
    // Your code here
}

Hint

Use let start = 0; and let end = numbers.len() - 1;.

3

Write the recursive binary search function

Write a recursive function called binary_search that takes numbers: &Vec, start: usize, end: usize, and target: i32. It should return i32. Implement the binary search logic to return the index of target or -1 if not found.

DSA Rust

fn main() {
    let numbers = vec![2, 4, 6, 8, 10, 12, 14];
    let start = 0;
    let end = numbers.len() - 1;
}

// Write the recursive binary_search function below
// Your code here

Hint

Use the middle index to compare and call binary_search recursively on the left or right half.

4

Call binary_search and print the result

Call binary_search with numbers, start, end, and target = 10. Print the returned index using println!

DSA Rust

fn main() {
    let numbers = vec![2, 4, 6, 8, 10, 12, 14];
    let start = 0;
    let end = numbers.len() - 1;
    // Call binary_search with target 10 and print the result
    // Your code here
}

fn binary_search(numbers: &Vec, start: usize, end: usize, target: i32) -> i32 {
    if start > end {
        return -1;
    }
    let mid = start + (end - start) / 2;
    if numbers[mid] == target {
        return mid as i32;
    } else if numbers[mid] > target {
        if mid == 0 {
            return -1;
        }
        return binary_search(numbers, start, mid - 1, target);
    } else {
        return binary_search(numbers, mid + 1, end, target);
    }
}

Hint

Use println!("{}", result); to print the index.

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