Binary Search vs Linear Search Real Cost Difference in DSA Rust - Interactive Comparison Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to perform a linear search that returns the index of the target or -1 if not found.

DSA Rust

fn linear_search(arr: &[i32], target: i32) -> i32 {
    for (index, &value) in arr.iter().enumerate() {
        if value == [1] {
            return index as i32;
        }
    }
    -1
}

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

Avalue

Bindex

Carr

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing index to target instead of value.

Returning value instead of index.

The function compares each element value with the target. When they match, it returns the current index.

2fill in blank

medium

Complete the code to perform a binary search on a sorted array and return the index of the target or -1 if not found.

DSA Rust

fn binary_search(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] == [1] {
            return mid;
        } else if arr[mid as usize] < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    -1
}

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

Atarget

Bleft

Cmid

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing middle element to left or right instead of target.

Using mid as the value instead of arr[mid].

The binary search compares the middle element arr[mid] with the target to decide the next search range.

3fill in blank

hard

Fix the error in the binary search code: complete the blank to correctly calculate the middle index without overflow.

DSA Rust

let mid = [1] + (right - left) / 2;

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

Aright

B0

Cleft

Dleft + right

Attempts:

3 left

💡 Hint

Common Mistakes

Using (left + right) / 2 which can overflow.

Using right alone as mid.

Calculating mid as left + (right - left) / 2 prevents overflow compared to (left + right) / 2.

4fill in blank

hard

Fill both blanks to create a Rust function that measures and compares the time taken by linear and binary search.

DSA Rust

use std::time::Instant;

fn compare_search_times(arr: &[i32], target: i32) {
    let start_linear = Instant::now();
    let _ = linear_search(arr, [1]);
    let duration_linear = start_linear.elapsed();

    let start_binary = Instant::now();
    let _ = binary_search(arr, [2]);
    let duration_binary = start_binary.elapsed();

    println!("Linear search took: {:?}", duration_linear);
    println!("Binary search took: {:?}", duration_binary);
}

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

Atarget

Barr.len() as i32 / 2

C0

Darr[0]

Attempts:

3 left

💡 Hint

Common Mistakes

Using different values for linear and binary search.

Passing an index instead of the target value.

Both searches should look for the same target value to fairly compare their times.

5fill in blank

hard

Fill all three blanks to create a Rust function that generates a sorted vector, searches for a target, and prints the results.

DSA Rust

fn main() {
    let arr: Vec<i32> = (1..=10000).map(|x| x [1] 1).collect();
    let target = 5000;
    let index_linear = linear_search(&arr, [2]);
    let index_binary = binary_search(&arr, [3]);
    println!("Linear Search found target at index: {}", index_linear);
    println!("Binary Search found target at index: {}", index_binary);
}

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

A-

B+

Ctarget

Dindex_linear

Attempts:

3 left

💡 Hint

Common Mistakes

Using - 1 which creates zero or negative values.

Searching for wrong variables instead of target.

The vector is generated by adding 1 to each number from 1 to 10000. Both searches look for the target value.

Practice

1. Which search method is generally faster on a sorted list of 1,000,000 elements?

easy

A. Depends on the element's position only

B. Linear Search

C. Both are equally fast

D. Binary Search

Solution

1. Step 1: Understand search methods on sorted lists

   Binary Search divides the list repeatedly, reducing search space quickly. Linear Search checks elements one by one.

2. Step 2: Compare time complexity for large lists

   Binary Search runs in O(log n) time, which is much faster than Linear Search's O(n) for large n like 1,000,000.

3. Final Answer:

   Binary Search -> Option D

4. Quick Check:

   Binary Search faster on sorted large lists [OK]

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

Common Mistakes:

• Thinking Linear Search is faster for sorted lists
• Ignoring list size impact
• Confusing sorted vs unsorted list performance

2. Which Rust code snippet correctly implements a linear search for a value in a slice?

easy

A. fn linear_search(arr: &[i32], target: i32) -> Option<usize> { let mut i = 0; while i < arr.len() { if arr[i] == target { return Some(i); } i += 1; } None }

B. fn linear_search(arr: &[i32], target: i32) -> Option<usize> { for i in 0..arr.len()-1 { if arr[i] == target { return Some(i); } } None }

C. fn linear_search(arr: &[i32], target: i32) -> usize { for i in 0..arr.len() { if arr[i] == target { return i; } } 0 }

D. fn linear_search(arr: &[i32], target: i32) -> Option<usize> { for i in 1..arr.len() { if arr[i] == target { return Some(i); } } None }

Solution

1. Step 1: Check function signature and return type

   Correct implementations should return Option<usize>, idiomatic for search functions. Returning plain usize with 0 on not found is ambiguous since index 0 is valid.

2. Step 2: Verify loop correctness and indexing

   The for loop from 0 to arr.len()-1 misses the last element. The while loop with mutable i from 0 while i < arr.len() covers all indices correctly. The for loop from 1 skips index 0.

3. Final Answer:

   While loop version -> Option A

4. Quick Check:

   Correct linear search loop and return [OK]

Hint: Check loop covers all indices and returns Option properly [OK]

Common Mistakes:

• Skipping first element in loop
• Returning ambiguous index instead of Option
• Incorrect loop bounds

3. What is the output of this Rust code using binary search on a sorted array?

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

medium

A. Err(2)

B. Ok(2)

C. Ok(3)

D. Err(3)

Solution

1. Step 1: Understand binary_search return type

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

2. Step 2: Find target index in array

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

3. Final Answer:

   Ok(2) -> Option B

4. Quick Check:

   binary_search returns Ok(index) when found [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 bug in this Rust binary search implementation and select the fix:

fn binary_search(arr: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = arr.len();
    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 - 1;
        }
    }
    None
}

medium

A. Change high initialization to arr.len() - 1

B. Change while condition to low > high

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

D. No bug, code is correct

Solution

1. Step 1: Analyze high variable initialization

   High is set to arr.len(), which is out of bounds since valid indices are 0 to arr.len()-1.

2. Step 2: Fix high initialization

   Set high to arr.len() - 1 to avoid index out of bounds error when accessing arr[mid].

3. Final Answer:

   Change high initialization to arr.len() - 1 -> Option A

4. Quick Check:

   High must be last valid index [OK]

Hint: High index must be last valid array index [OK]

Common Mistakes:

• Using arr.len() as high causes out of bounds
• Changing while condition incorrectly
• Ignoring mid calculation overflow

5. You have a sorted list of 10,000 elements and want to find if a value exists. Which approach minimizes average search steps considering the cost of comparisons and index calculations?

Assume:
- Each comparison costs 1 unit
- Each index calculation (like mid) costs 2 units
- Linear search does only comparisons
- Binary search does comparisons + index calculations per step

hard

A. Linear search is cheaper because it avoids index calculations

B. Both have equal cost on average

C. Binary search is cheaper because it reduces comparisons drastically despite index costs

D. Linear search is cheaper only if the element is near the start

Solution

1. Step 1: Calculate linear search average cost

   Linear search average steps = n/2 = 5000 comparisons, cost = 5000 * 1 = 5000 units.

2. Step 2: Calculate binary search average cost

   Binary search steps = log2(10000) ≈ 14 steps. Each step costs 1 (comparison) + 2 (index calc) = 3 units. Total = 14 * 3 = 42 units.

3. Step 3: Compare costs

   42 units (binary) << 5000 units (linear), so binary search is cheaper on average.

4. Final Answer:

   Binary search is cheaper because it reduces comparisons drastically despite index costs -> Option C

5. Quick Check:

   Binary search cost << Linear search cost [OK]

Hint: Binary search steps grow logarithmically, beating linear cost [OK]

Common Mistakes:

• Ignoring index calculation cost
• Assuming linear search always cheaper
• Misestimating average steps