Binary Search as Divide and Conquer in DSA Rust

Mental Model

Binary search splits a sorted list into halves repeatedly to find a target quickly.

Analogy: Like guessing a number between 1 and 100 by asking if it's higher or lower than your guess, cutting the range in half each time.

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indices:     [0, 1, 2, 3, 4,  5,  6]
Search range: ↑--------------------↑
             low                 high

Dry Run Walkthrough

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

Goal: Find the index of target 9 in the array using binary search

Step 1: Calculate middle index between low=0 and high=6, mid=3; check value at mid=7

[1, 3, 5, [7], 9, 11, 13]
low=0, mid=3, high=6

Why: We check middle to decide which half to search next

Step 2: Since 7 < 9, move low to mid+1=4 to search right half

[1, 3, 5, 7, [9], 11, 13]
low=4, high=6

Why: Target must be in right half because 9 is greater than 7

Step 3: Calculate middle index between low=4 and high=6, mid=5; check value at mid=11

[1, 3, 5, 7, 9, [11], 13]
low=4, mid=5, high=6

Why: Check middle of new range to narrow search

Step 4: Since 11 > 9, move high to mid-1=4 to search left half

[1, 3, 5, 7, [9], 11, 13]
low=4, high=4

Why: Target must be in left half because 9 is less than 11

Step 5: Calculate middle index between low=4 and high=4, mid=4; check value at mid=9

[1, 3, 5, 7, [9], 11, 13]
low=4, mid=4, high=4

Why: Check the last remaining element

Step 6: Value at mid equals target 9, return index 4

[1, 3, 5, 7, [9], 11, 13]
Found target at index 4

Why: Target found, search ends

Result:

[1, 3, 5, 7, [9], 11, 13]
Target 9 found at index 4

Annotated Code

DSA Rust

fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    if arr.is_empty() {
        return None;
    }
    let mut high = arr.len() - 1;

    while low <= high {
        let mid = low + (high - low) / 2; // find middle index
        if arr[mid] == target {
            return Some(mid); // target found
        } else if arr[mid] < target {
            low = mid + 1; // search right half
        } else {
            if mid == 0 { break; } // prevent underflow
            high = mid - 1; // search left half
        }
    }
    None // target not found
}

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

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

Calculate middle index to split search range

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

Check if middle element is the target

else if arr[mid] < target { low = mid + 1; }

If middle element less than target, search right half

else { if mid == 0 { break; } high = mid - 1; }

If middle element greater than target, search left half; prevent underflow

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range, quickly narrowing down the target

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted data by dividing the problem repeatedly

Edge Cases

empty array

function returns None immediately because high index underflows and loop doesn't run

DSA Rust

if arr.is_empty() { return None; }

target smaller than all elements

search narrows to empty range and returns None

DSA Rust

while low <= high { ... }

target larger than all elements

search narrows to empty range and returns None

DSA Rust

while low <= high { ... }

target at first index

found quickly when mid points to first element

DSA Rust

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

When to Use This Pattern

When you need to find an item quickly in a sorted list, use binary search because it divides the problem in half each step, making it very fast.

Common Mistakes

Mistake: Calculating mid as (low + high) can cause integer overflow
Fix: Calculate mid as low + (high - low) / 2 to avoid overflow

Mistake: Not handling the case when mid is 0 before subtracting 1 from high, causing underflow
Fix: Add a check to break loop if mid is 0 before setting high = mid - 1

Mistake: Using binary search on unsorted arrays
Fix: Ensure array is sorted before applying binary search

Summary

Binary search finds a target in a sorted array by repeatedly dividing the search range in half.

Use it when you have a sorted list and want to find an element quickly.

The key insight is cutting the search space in half each step to reduce work exponentially.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. Sort the list first, then search linearly

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

C. Repeatedly split the sorted list in half to find the target

D. Use a hash table to find the target instantly

Solution

1. Step 1: Understand divide and conquer in binary search

   Binary search works by dividing the sorted list into two halves and deciding which half to search next.

2. Step 2: Identify the correct approach

   It repeatedly splits the list in half, narrowing down the search space until the target is found or no elements remain.

3. Final Answer:

   Repeatedly split the sorted list in half to find the target -> Option C

4. Quick Check:

   Divide and conquer = split list halves [OK]

Hint: Binary search halves the list each step [OK]

Common Mistakes:

• Thinking binary search checks every element
• Assuming list must be unsorted
• Confusing binary search with linear search

2. Which of the following is the correct Rust function signature for a binary search function that returns an Option<usize>?

easy

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

B. fn binary_search(arr: Vec bool

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

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

Solution

1. Step 1: Understand Rust function signature for binary search

   The function takes a slice of integers and a target integer, returning an Option with the index if found.

2. Step 2: Match the correct signature

   Option<usize> is used to return Some(index) if found or None if not found, matching fn binary_search(arr: &[i32], target: i32) -> Option<usize>.

3. Final Answer:

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

4. Quick Check:

   Return Option<usize> for index or None [OK]

Hint: Use Option<usize> to handle found or not found [OK]

Common Mistakes:

• Returning usize without Option causes errors if not found
• Using Vec instead of slice for input unnecessarily
• Returning bool loses index information

3. What will be the output of this Rust code snippet using binary search?

fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len() - 1;
    while left <= right {
        let mid = left + (right - left) / 2;
        if arr[mid] == target {
            return Some(mid);
        } else if arr[mid] < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    None
}

fn main() {
    let nums = [2, 4, 6, 8, 10];
    println!("{:?}", binary_search(&nums, 6));
}

medium

A. Some(3)

B. Some(2)

C. None

D. Some(1)

Solution

1. Step 1: Trace binary search on array [2,4,6,8,10] for target 6

   Initial left=0, right=4, mid=2. arr[2]=6 matches target.

2. Step 2: Return index 2 wrapped in Some

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

3. Final Answer:

   Some(2) -> Option B

4. Quick Check:

   Index of 6 in array is 2 [OK]

Hint: Check mid index value equals target first [OK]

Common Mistakes:

• Off-by-one errors in mid calculation
• Confusing index with value
• Returning None incorrectly when target exists

4. Identify the bug in this binary search Rust code and choose the correct fix:

fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len();
    while left <= right {
        let mid = left + (right - left) / 2;
        if arr[mid] == target {
            return Some(mid);
        } else if arr[mid] < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    None
}

medium

A. Change while condition to left < right

B. Change mid calculation to (left + right) / 2 without subtraction

C. Remove else if and use only if and else

D. Change right initialization to arr.len() - 1

Solution

1. Step 1: Analyze right boundary initialization

   Right is set to arr.len(), which is out of bounds since indexing is 0-based.

2. Step 2: Fix right to arr.len() - 1 to avoid out-of-bounds access

   Setting right to arr.len() - 1 ensures mid index stays within valid range.

3. Final Answer:

   Change right initialization to arr.len() - 1 -> Option D

4. Quick Check:

   Right boundary must be last valid index [OK]

Hint: Right index = length - 1 for zero-based arrays [OK]

Common Mistakes:

• Using arr.len() as right causes panic
• Changing while condition incorrectly
• Incorrect mid calculation causing overflow

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

hard

A. After finding target at mid, continue searching left half to find earlier occurrence

B. Return immediately when target is found at mid

C. Search right half only after finding target

D. Use linear search after binary search to find first occurrence

Solution

1. Step 1: Understand duplicates and first occurrence requirement

   Binary search normally returns any matching index, but to find first occurrence, we must check if earlier duplicates exist.

2. Step 2: Modify search to continue left after finding target

   When target is found at mid, record index and continue searching left half to find if an earlier occurrence exists.

3. Final Answer:

   After finding target at mid, continue searching left half to find earlier occurrence -> Option A

4. Quick Check:

   Find first occurrence by searching left after match [OK]

Hint: Keep searching left half after finding target [OK]

Common Mistakes:

• Stopping search immediately on first match
• Searching right half instead of left
• Using linear search unnecessarily