Why Binary Search and What Sorted Order Gives You in DSA Rust - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle index in binary search.

DSA Rust

let mid = (low + [1]) / 2;

Drag options to blanks, or click blank then click option'

Amid

Bstart

Clow

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Using low twice instead of low and high.

Using mid variable before it's defined.

In binary search, the middle index is calculated by averaging the low and high indices.

2fill in blank

medium

Complete the code to compare the middle element with the target.

DSA Rust

if arr[mid] [1] target {

Drag options to blanks, or click blank then click option'

A==

B<=

C>=

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using inequality operators instead of equality.

Confusing comparison direction.

We check if the middle element equals the target to find the item.

3fill in blank

hard

Fix the error in updating the low index when target is greater than middle element.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Alow + 1

Bmid

Cmid + 1

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Setting low to mid causes infinite loop.

Setting low to high skips elements.

We move low to mid + 1 to search the right half excluding mid.

4fill in blank

hard

Fill both blanks to update high index when target is less than middle element.

DSA Rust

if arr[mid] > target {
    [1] = [2];
}

Drag options to blanks, or click blank then click option'

Ahigh

Bmid

Cmid - 1

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Setting high to mid causes infinite loop.

Setting high to low skips elements.

We set high to mid - 1 to search the left half excluding mid.

5fill in blank

hard

Fill all three blanks to complete the binary search loop condition and return statement.

DSA Rust

while [1] <= [2] {
    let mid = (low + high) / 2;
    if arr[mid] == target {
        return [3];
    }
    // update low or high
}

Drag options to blanks, or click blank then click option'

Alow

Bhigh

Cmid

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Using target instead of mid in return.

Wrong loop condition causing infinite loop.

The loop runs while low is less or equal to high. Return mid when found.

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