Why Binary Search and What Sorted Order Gives You in DSA Rust - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this binary search code?

Consider the Rust code below that performs a binary search on a sorted array. What will it print?

DSA Rust

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

fn main() {
    let sorted_arr = [2, 4, 6, 8, 10, 12];
    match binary_search(&sorted_arr, 8) {
        Some(index) => println!("Found at index {}", index),
        None => println!("Not found"),
    }
}

A Found at index 3

B Found at index 2

C Not found

D Runtime panic due to index out of bounds

💡 Hint

Remember that array indexing starts at 0 and the array is sorted.

The binary search finds the target 8 at index 3 in the sorted array [2,4,6,8,10,12]. The code correctly calculates mid and adjusts low and high pointers.

🧠 Conceptual

intermediate

Why must the array be sorted for binary search?

Why is it necessary for the array to be sorted before performing a binary search?

A Because binary search only works on arrays with unique elements.

B Because binary search compares the target with the middle element and decides which half to search next, which only works if the array is sorted.

C Because binary search requires the array to be reversed.

D Because binary search can only find the first element in any array.

💡 Hint

Think about how binary search decides which part of the array to ignore.

Binary search relies on the sorted order to eliminate half of the search space each time by comparing the target with the middle element.

❓ Predict Output

advanced

What happens if binary search is run on an unsorted array?

Given the Rust code below, what will be the output when searching for 5 in the unsorted array?

DSA Rust

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

fn main() {
    let unsorted_arr = [10, 2, 8, 6, 4];
    match binary_search(&unsorted_arr, 5) {
        Some(index) => println!("Found at index {}", index),
        None => println!("Not found"),
    }
}

A Found at index 4

B Found at index 1

C Not found

D Runtime panic due to index out of bounds

💡 Hint

Binary search assumes sorted order; what happens if the array is not sorted?

Binary search on an unsorted array does not guarantee finding the target. Here, 5 is not in the array, so it returns None and prints "Not found".

🔧 Debug

advanced

Why does this binary search code panic on empty array?

Look at the Rust code below. What causes a runtime panic when calling binary_search on an empty array?

DSA Rust

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

fn main() {
    let empty_arr: [i32; 0] = [];
    match binary_search(&empty_arr, 1) {
        Some(index) => println!("Found at index {}", index),
        None => println!("Not found"),
    }
}

A Because mid calculation uses floating point division.

B Because the while loop condition low <= high is always false for empty arrays.

C Because the target 1 is not in the array.

D Because arr.len() - 1 causes underflow when array is empty, leading to panic.

💡 Hint

Check what happens when subtracting 1 from zero in unsigned integers.

When the array is empty, arr.len() is 0, so arr.len() - 1 underflows to a very large number, causing out-of-bounds access and panic.

🚀 Application

expert

How many comparisons does binary search make to find an element in a sorted array of size 64?

Binary search halves the search space each time. How many maximum comparisons are needed to find an element or conclude it is not present in a sorted array of 64 elements?

A 7

B 8

C 6

D 64

💡 Hint

Think about how many times you can divide 64 by 2 until you reach 1.

Binary search requires at most log2(n) + 1 comparisons. For 64 elements, log2(64) = 6, so maximum comparisons are 7.

Practice

1. Why is binary search only applicable on a sorted list?

easy

A. Because binary search works on unsorted lists by checking every element

B. Because binary search can only work on lists with unique elements

C. Because binary search divides the list and compares middle elements, which only works if the list is sorted

D. Because binary search requires the list to be reversed

Solution

1. Step 1: Understand binary search method

   Binary search works by repeatedly dividing the list and comparing the middle element to the target.

2. Step 2: Importance of sorted order

   This division and comparison only make sense if the list is sorted, so we know which half to discard.

3. Final Answer:

   Because binary search divides the list and compares middle elements, which only works if the list is sorted -> Option C

4. Quick Check:

   Sorted list needed for binary search = True [OK]

Hint: Binary search needs sorted data to decide halves quickly [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Believing binary search requires unique elements
• Confusing binary search with linear search

2. Which of the following Rust code snippets correctly declares a sorted vector for binary search?

easy

A. let v = vec![1, 2, 3, 4];

B. let v = vec![3, 1, 4, 2];

C. let v = vec![4, 3, 2, 1];

D. let v = vec!["apple", "banana", "cherry"];

Solution

1. Step 1: Identify sorted vector

   Binary search requires the vector to be sorted in ascending order. let v = vec![1, 2, 3, 4]; is sorted ascending: 1, 2, 3, 4.

2. Step 2: Check other options

   let v = vec![3, 1, 4, 2]; is unsorted. let v = vec![4, 3, 2, 1]; is sorted descending, which is not standard for binary search. let v = vec!["apple", "banana", "cherry"]; is sorted alphabetically but contains strings, not integers.

3. Final Answer:

   let v = vec![1, 2, 3, 4]; -> Option A

4. Quick Check:

   Sorted vector for binary search = let v = vec![1, 2, 3, 4]; [OK]

Hint: Binary search needs ascending sorted vector [OK]

Common Mistakes:

• Using unsorted vectors for binary search
• Assuming descending order works without modification
• Mixing data types in vector

3. What will be the output of this Rust code using binary search on a sorted vector?

let v = vec![2, 4, 6, 8, 10];
let result = v.binary_search(&6);
println!("{:?}", result);

medium

A. Ok(2)

B. Ok(3)

C. Err(2)

D. Err(3)

Solution

1. Step 1: Understand binary_search return

   binary_search returns Ok(index) if found, Err(insert_pos) if not found.

2. Step 2: Find index of 6 in vector

   Vector is [2,4,6,8,10]. 6 is at index 2 (0-based).

3. Final Answer:

   Ok(2) -> Option A

4. Quick Check:

   Index of 6 = 2, so output = Ok(2) [OK]

Hint: binary_search returns Ok(index) if found [OK]

Common Mistakes:

• Confusing Ok and Err results
• Miscounting zero-based index
• Assuming Err means found

4. Identify the error in this Rust code that attempts binary search on an unsorted vector:

let v = vec![5, 3, 8, 1];
let result = v.binary_search(&3);
println!("{:?}", result);

medium

A. No error, code runs and returns Ok(1)

B. Logical error: vector is unsorted, so binary_search result is unreliable

C. No error, code runs but returns Err(1)

D. Syntax error: binary_search requires mutable vector

Solution

1. Step 1: Check vector order

   The vector is [5, 3, 8, 1], which is unsorted.

2. Step 2: Understand binary_search requirement

   binary_search requires sorted vectors; otherwise, the result is unpredictable or incorrect.

3. Final Answer:

   Logical error: vector is unsorted, so binary_search result is unreliable -> Option B

4. Quick Check:

   Unsorted vector breaks binary_search logic [OK]

Hint: Always sort vector before binary_search [OK]

Common Mistakes:

• Assuming binary_search works on unsorted vectors
• Confusing syntax errors with logical errors
• Thinking binary_search needs mutable vector

5. Given a sorted vector v = vec![1, 3, 5, 7, 9], how can you find the position to insert 6 to keep the vector sorted using binary search?

hard

A. Use v.binary_search(&6) which returns Ok(2)

B. Use v.iter().position(|&x| x > 6) which returns 2

C. Use v.binary_search(&6) which returns Err(2)

D. Use v.binary_search(&6) which returns Err(3)

Solution

1. Step 1: Understand binary_search return for missing element

   When element is not found, binary_search returns Err(insert_pos) where insert_pos is the index to insert to keep sorted order.

2. Step 2: Find insert position for 6 in vector

   Vector is [1,3,5,7,9]. 6 fits between 5 (index 2) and 7 (index 3), so insert position is 3.

3. Final Answer:

   Use v.binary_search(&6) which returns Err(3) -> Option D

4. Quick Check:

   Insert position for 6 = 3, so Err(3) returned [OK]

Hint: binary_search returns Err(insert_pos) if not found [OK]

Common Mistakes:

• Confusing Ok and Err results
• Misunderstanding insert position index
• Using iterator position instead of binary_search