Binary Search Iterative Approach in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search Iterative for Present Element

What is the output of the following Rust code that performs an iterative binary search for the value 7 in a sorted array?

DSA Rust

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

fn main() {
    let arr = [1, 3, 5, 7, 9, 11];
    let index = binary_search_iterative(&arr, 7);
    println!("{}", index);
}

A -1

B 2

C 4

D 3

💡 Hint

Remember that array indices start at 0 and 7 is the fourth element in the array.

The array is [1, 3, 5, 7, 9, 11]. The value 7 is at index 3 (0-based). The binary search finds it and returns index 3.

❓ Predict Output

intermediate

Output of Binary Search Iterative for Missing Element

What is the output of the following Rust code that performs an iterative binary search for the value 8 in a sorted array?

DSA Rust

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

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

A 2

B 3

C -1

D 0

💡 Hint

If the target is not found, the function returns -1.

The array is [2, 4, 6, 10, 12]. The value 8 is not in the array. The function returns -1 to indicate not found.

🧠 Conceptual

advanced

Why use mid = left + (right - left) / 2 in Binary Search?

In the iterative binary search, why is the middle index calculated as mid = left + (right - left) / 2 instead of mid = (left + right) / 2?

A To make the code shorter and easier to read

B To prevent integer overflow when left and right are large values

C Because (left + right) / 2 is not a valid expression in Rust

D To always round up the middle index

💡 Hint

Think about what happens if left and right are very large numbers.

Using left + (right - left) / 2 avoids potential overflow when left + right exceeds the maximum integer value.

🔧 Debug

advanced

Identify the Bug in Binary Search Iterative Code

What error will occur when running this Rust code for binary search?

DSA Rust

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

fn main() {
    let arr = [1, 2, 3, 4, 5];
    let index = binary_search_iterative(&arr, 3);
    println!("{}", index);
}

A Index out of bounds panic at runtime

B Compilation error due to type mismatch

C Infinite loop causing program to hang

D Returns -1 even if element is present

💡 Hint

Check how right is initialized and used as an index.

The variable right is initialized to arr.len(), which is one past the last valid index. Accessing arr[mid] can cause an index out of bounds panic.

🚀 Application

expert

Number of Iterations in Binary Search

Given a sorted array of length 64, what is the maximum number of iterations the iterative binary search algorithm will perform to find a target or conclude it is not present?

A 7

B 8

C 64

D 6

💡 Hint

Binary search halves the search space each iteration. Think about powers of 2.

Binary search reduces the search space by half each iteration. For 64 elements, maximum iterations = log2(64) + 1 = 6 + 1 = 7.

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