Binary Search as Divide and Conquer in DSA Rust - Execution Trace

Concept Flow - Binary Search as Divide and Conquer

Start with sorted array and target

↓

Set low and high indices

↓

Calculate mid index

↓

Compare target with mid element

↓

Search right half

↓

Search left half

↓

Repeat until low > high

↓

Target not found

Binary search splits the sorted array into halves repeatedly, comparing the target with the middle element to decide which half to search next.

Execution Sample

DSA Rust

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

This code searches for a target number in a sorted array using binary search and returns its index if found.

Execution Table

Step	Operation	Low	High	Mid	Compare arr[mid] with target	Action	Array State
1	Initialize low and high	0	6	-	-	Set low=0, high=6	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	arr[3]=7 vs target=9	7 < 9 → search right half	[1, 3, 5, 7, 9, 11, 13]
3	Update low	4	6	-	-	low = mid + 1 = 4	[1, 3, 5, 7, 9, 11, 13]
4	Calculate mid	4	6	5	arr[5]=11 vs target=9	11 > 9 → search left half	[1, 3, 5, 7, 9, 11, 13]
5	Update high	4	4	-	-	high = mid - 1 = 4	[1, 3, 5, 7, 9, 11, 13]
6	Calculate mid	4	4	4	arr[4]=9 vs target=9	Found target at index 4	[1, 3, 5, 7, 9, 11, 13]
7	Return result	4	4	4	-	Return Some(4)	[1, 3, 5, 7, 9, 11, 13]

💡 Target found at index 4, search ends.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
low	0	0	4	4	4	4	4
high	6	6	6	6	4	4	4
mid	-	3	-	5	-	4	4

Key Moments - 3 Insights

Why do we update 'low' to mid + 1 when arr[mid] < target?

Because arr[mid] is less than target, the target must be in the right half beyond mid. So we set low to mid + 1 to search only that half (see Step 2 and Step 3 in execution_table).

Why do we update 'high' to mid - 1 when arr[mid] > target?

Because arr[mid] is greater than target, the target must be in the left half before mid. So we set high to mid - 1 to search only that half (see Step 4 and Step 5 in execution_table).

Why does the loop stop when low > high?

When low passes high, it means the search space is empty and the target is not found. The loop ends without finding the target (not shown here because target was found).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the value of 'mid'?

A 3

B 5

C 4

D 6

💡 Hint

Check the 'Mid' column in execution_table row for Step 4.

At which step does the algorithm update 'high' to 4?

A Step 3

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Action' column where 'high' is set to mid - 1.

If the target was 12 instead of 9, what would happen after Step 4?

A low would be updated to 6

B high would be updated to 4

C target found at index 5

D loop ends immediately

💡 Hint

Consider that 11 < 12, so search moves to right half after Step 4.

Concept Snapshot

Binary Search divides a sorted array by comparing the target with the middle element.
If target equals middle, return index.
If target is less, search left half (high = mid - 1).
If target is more, search right half (low = mid + 1).
Repeat until low > high (target not found).
Efficient O(log n) search method.

Full Transcript

Binary search works on sorted arrays by repeatedly dividing the search space in half. We start with low and high indices covering the whole array. We calculate the middle index and compare the middle element with the target. If they match, we return the index. If the target is greater, we move low to mid + 1 to search the right half. If the target is smaller, we move high to mid - 1 to search the left half. This process repeats until low exceeds high, meaning the target is not in the array. This method quickly narrows down the search area, making it very efficient.

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