Binary Search Iterative Approach in DSA Rust

Mental Model

Binary search repeatedly cuts the list in half to quickly find a target value.

Analogy: Like guessing a number between 1 and 100 by asking if it is higher or lower than your guess, narrowing down the range each time.

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Pointers:  low ↑                 high ↑
Mid points to middle element

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 iterative binary search

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

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Pointers: low=0 ↑ mid=3 ↑ high=6 ↑

Why: We start by checking the middle element to decide which half to search next

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

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Pointers: low=4 ↑       high=6 ↑

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

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

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Pointers: low=4 ↑ mid=5 ↑ high=6 ↑

Why: Check middle of the new search range

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

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Pointers: low=4 ↑       high=4 ↑

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

Step 5: Calculate mid between low=4 and high=4, mid=4, check value 9

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Pointers: low=4 ↑ mid=4 ↑ high=4 ↑

Why: Only one element left to check

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

Array: [1, 3, 5, 7, 9, 11, 13]
Indexes:  0  1  2  3  4   5   6
Pointers: mid=4 ↑

Why: Found the target value at index 4

Result:

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

Annotated Code

DSA Rust

fn binary_search_iterative(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 - low) / 2; // calculate mid index
        if arr[mid] == target {
            return Some(mid); // found target
        } 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_iterative(&arr, target) {
        Some(index) => println!("Found target {} at index {}", target, index),
        None => println!("Target {} not found", target),
    }
}

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

calculate middle index to split search range

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

check if middle element is target

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

move low pointer to right half if target is greater

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

move high pointer to left half if target is smaller, prevent underflow

Output

Found target 9 at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range until the target is found or range is empty

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 arrays by cutting search space in half each step

Edge Cases

empty array

function returns None immediately because high underflows and loop does not run

DSA Rust

while low <= high {

target smaller than all elements

search narrows until low > high and returns None

DSA Rust

while low <= high {

target larger than all elements

search narrows until low > high and returns None

DSA Rust

while low <= high {

target at first index

found quickly when mid points to index 0

DSA Rust

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

target at last index

found when mid points to last index after narrowing search

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 iterative approach because it efficiently halves the search space each step.

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 the loop if mid is 0 before doing high = mid - 1.

Mistake: Using recursion instead of iterative approach when iterative is requested.
Fix: Use a while loop with low and high pointers instead of recursive calls.

Summary

It finds the position of a target value 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 to compare the target with the middle element and narrow the search range accordingly.

Practice

1. What is the main purpose of the binary search iterative approach in a sorted array?

easy

A. To find the position of a target value efficiently by repeatedly dividing the search interval in half

B. To sort the array elements in ascending order

C. To reverse the array elements

D. To find the maximum value in the array

Solution

1. Step 1: Understand binary search goal

   Binary search aims to find a target value's position in a sorted array quickly by dividing the search range repeatedly.

2. Step 2: Compare with other options

   Sorting, reversing, or finding max are different operations unrelated to binary search's main goal.

3. Final Answer:

   To find the position of a target value efficiently by repeatedly dividing the search interval in half -> Option A

4. Quick Check:

   Binary search = divide and conquer search [OK]

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

Common Mistakes:

• Confusing binary search with sorting algorithms
• Thinking binary search works on unsorted arrays
• Assuming binary search finds max or min values

2. Which of the following is the correct Rust syntax to start the iterative binary search loop over a sorted slice arr with indices low and high?

easy

A. while low <= high { /* loop body */ }

B. for i in low..high { /* loop body */ }

C. loop { if low > high { break; } /* loop body */ }

D. while low < high { /* loop body */ }

Solution

1. Step 1: Identify correct loop condition for binary search

   Binary search continues while low index is less than or equal to high index to cover all elements.

2. Step 2: Compare options

   while low <= high { /* loop body */ } uses while low <= high, which is correct. for i in low..high { /* loop body */ } uses a for loop which is not suitable. loop { if low > high { break; } /* loop body */ } uses an infinite loop with break, which is less clear. while low < high { /* loop body */ } uses low < high, which misses the case when low equals high.

3. Final Answer:

   while low <= high { /* loop body */ } -> Option A

4. Quick Check:

   Loop condition includes equality for last element [OK]

Hint: Use while low <= high to cover all elements [OK]

Common Mistakes:

• Using for loop instead of while for binary search
• Using < instead of <= causing missed element check
• Using infinite loop without proper break condition

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

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

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

medium

A. -1

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace binary search for target 6 in array

   Array is [2,4,6,8,10]. Initial low=0, high=4. mid=2. arr[2]=6 equals target, so return 2.

2. Step 2: Confirm returned index

   Index 2 is correct position of 6 in the array.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Target 6 found at index 2 [OK]

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

Common Mistakes:

• Miscomputing mid index causing wrong return
• Returning -1 incorrectly when target exists
• Confusing index with value in output

4. Identify the error in this Rust iterative binary search function and choose the fix:

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

medium

A. Change while condition to low < high

B. Remove type casting of mid to usize

C. Change mid calculation to mid = low - (high - low) / 2

D. Change high initialization to arr.len() as i32 - 1

Solution

1. Step 1: Analyze high initialization

   High is set to arr.len() which is out of bounds index (since last valid index is length - 1).

2. Step 2: Correct high initialization

   Set high to arr.len() - 1 to avoid index out of bounds error during access.

3. Final Answer:

   Change high initialization to arr.len() as i32 - 1 -> Option D

4. Quick Check:

   High must be last valid index [OK]

Hint: High index = length - 1 to avoid out of bounds [OK]

Common Mistakes:

• Setting high to length causing panic
• Changing while condition incorrectly
• Incorrect mid calculation formula

5. Given a sorted array arr = [1, 3, 5, 7, 9, 11], write an iterative binary search function in Rust to find the index of the smallest element greater than or equal to a target value. What will be the output of your function when searching for target 8?

hard

A. 5

B. 4

C. -1

D. 3

Solution

1. Step 1: Understand problem - find smallest element >= target

   We want the index of the first element not less than target 8.

2. Step 2: Trace binary search for target 8

   Array: [1,3,5,7,9,11]. Elements >=8 are 9 (index 4) and 11 (index 5). The smallest is 9 at index 4.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   First element >= 8 is 9 at index 4 [OK]

Hint: Find first element >= target by adjusting high on match [OK]

Common Mistakes:

• Returning index of element just less than target
• Returning -1 when element exists
• Confusing smallest element greater than target with equal