Linear Search Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of linear search when element is present

What is the output of this Rust code that performs a linear search for the value 7 in the array?

DSA Rust

fn linear_search(arr: &[i32], target: i32) -> Option<usize> {
    for (index, &value) in arr.iter().enumerate() {
        if value == target {
            return Some(index);
        }
    }
    None
}

fn main() {
    let numbers = [3, 5, 7, 9, 11];
    match linear_search(&numbers, 7) {
        Some(index) => println!("Found at index {}", index),
        None => println!("Not found"),
    }
}

A Found at index 1

B Found at index 3

C Not found

D Found at index 2

💡 Hint

Remember that Rust arrays are zero-indexed, so the first element is at index 0.

The linear search checks each element in order. The value 7 is at the third position, which is index 2 (starting from 0). So the output is 'Found at index 2'.

❓ Predict Output

intermediate

Output when element is not in the array

What will this Rust code print when searching for 10 in the array?

DSA Rust

fn linear_search(arr: &[i32], target: i32) -> Option<usize> {
    for (index, &value) in arr.iter().enumerate() {
        if value == target {
            return Some(index);
        }
    }
    None
}

fn main() {
    let numbers = [1, 2, 3, 4, 5];
    match linear_search(&numbers, 10) {
        Some(index) => println!("Found at index {}", index),
        None => println!("Not found"),
    }
}

A Found at index 0

B Found at index 4

C Not found

D Found at index 5

💡 Hint

Check if the target value exists in the array.

The value 10 is not in the array, so the function returns None and the program prints 'Not found'.

🧠 Conceptual

advanced

Time complexity of linear search

What is the worst-case time complexity of the linear search algorithm when searching for an element in an array of size n?

A O(n)

B O(1)

C O(n log n)

D O(log n)

💡 Hint

Consider how many elements might be checked in the worst case.

In the worst case, linear search checks every element once, so it takes O(n) time.

🔧 Debug

advanced

Identify the error in this linear search implementation

What error will this Rust code produce when compiled?

DSA Rust

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

A TypeError: mismatched types

B SyntaxError: expected `==` but found `=`

C Runtime panic: index out of bounds

D No error, code runs correctly

💡 Hint

Check the comparison operator inside the if condition.

The code uses a single equals sign `=` (assignment) instead of `==` (comparison). Assignment returns `()` but `if` expects `bool`, causing mismatched types.

🚀 Application

expert

Result of linear search on a large array with duplicates

Given this Rust code searching for 42 in an array with duplicates, what is the output?

DSA Rust

fn linear_search(arr: &[i32], target: i32) -> Option<usize> {
    for (index, &value) in arr.iter().enumerate() {
        if value == target {
            return Some(index);
        }
    }
    None
}

fn main() {
    let numbers = [10, 42, 23, 42, 5, 42];
    match linear_search(&numbers, 42) {
        Some(index) => println!("Found at index {}", index),
        None => println!("Not found"),
    }
}

A Found at index 3

B Found at index 1

C Found at index 5

D Not found

💡 Hint

Linear search returns the first occurrence of the target.

The first 42 appears at index 1, so the function returns Some(1) and prints 'Found at index 1'.

Practice

1. What is the main idea behind the Linear Search Algorithm?

easy

A. Divide the list into halves repeatedly to find the target

B. Use a hash table to find the target instantly

C. Sort the list first then search using binary steps

D. Check each element one by one until the target is found or list ends

Solution

1. Step 1: Understand linear search process

   Linear search checks each element in order from start to end.

2. Step 2: Compare with other search methods

   Binary search divides list, hash uses extra memory, linear is simple sequential check.

3. Final Answer:

   Check each element one by one until the target is found or list ends -> Option D

4. Quick Check:

   Linear search = sequential check [OK]

Hint: Linear search means checking items one by one [OK]

Common Mistakes:

• Confusing linear search with binary search
• Thinking linear search requires sorted data
• Assuming linear search uses extra memory

2. Which of the following is the correct Rust syntax to start a linear search loop over a vector arr?

easy

A. while i < arr.len() { }

B. for i in arr { }

C. for i in 0..arr.len() { }

D. loop i in arr.len() { }

Solution

1. Step 1: Identify correct Rust for loop syntax

   Rust uses for i in 0..arr.len() to loop over indices.

2. Step 2: Check other options for syntax errors

   for i in arr iterates over values, not indices; while needs initialization; loop i in is invalid.

3. Final Answer:

   for i in 0..arr.len() { } -> Option C

4. Quick Check:

   Rust for loop over range = for i in 0..len() [OK]

Hint: Use for i in 0..arr.len() to loop indices [OK]

Common Mistakes:

• Using for i in arr to get indices instead of values
• Writing invalid loop syntax like loop i in ...
• Forgetting to initialize loop variable in while loops

3. What will be the output of this Rust code snippet?

let arr = vec![3, 5, 7, 9];
let target = 7;
let mut index = -1;
for i in 0..arr.len() {
    if arr[i] == target {
        index = i as i32;
        break;
    }
}
println!("{}", index);

medium

A. 0

B. 2

C. 3

D. -1

Solution

1. Step 1: Trace the loop to find target index

   Loop checks arr[0]=3, arr[1]=5, arr[2]=7 matches target, sets index=2 and breaks.

2. Step 2: Print the index value

   After break, index is 2, so printed output is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Target 7 found at index 2 [OK]

Hint: Stop loop at first match, print that index [OK]

Common Mistakes:

• Not breaking loop after finding target
• Printing index before loop ends
• Confusing index type casting

4. Identify the error in this Rust linear search code and choose the fix:

let arr = vec![1, 2, 3];
let target = 4;
let mut found = false;
for i in 0..arr.len() {
    if arr[i] = target {
        found = true;
        break;
    }
}
println!("{}", found);

medium

A. Use '==' for comparison instead of '='

B. Change 'found' to integer type

C. Remove the break statement

D. Use while loop instead of for loop

Solution

1. Step 1: Check the if condition syntax

   The code uses '=' which is assignment, not comparison. It should be '==' to compare values.

2. Step 2: Verify other options

   Changing 'found' type or removing break won't fix syntax error. Using while loop is valid but not necessary.

3. Final Answer:

   Use '==' for comparison instead of '=' -> Option A

4. Quick Check:

   Comparison needs '==' not '=' [OK]

Hint: Use '==' to compare values, '=' assigns [OK]

Common Mistakes:

• Using '=' instead of '==' in if conditions
• Removing break causing unnecessary iterations
• Changing variable types unnecessarily

5. You want to find all indices of a target value in a vector arr using linear search in Rust. Which approach correctly collects all matching indices?

hard

A. Use a loop over indices, push index to a vector when element equals target

B. Break the loop at first match and return that index

C. Sort the vector first, then use binary search for all matches

D. Use a hash map to store element counts and find indices

Solution

1. Step 1: Understand requirement to find all indices

   We must check every element and collect indices where element equals target.

2. Step 2: Evaluate options for correctness

   Breaking loop stops early, sorting changes order, hash map counts but doesn't store indices. Only pushing indices in loop works.

3. Final Answer:

   Use a loop over indices, push index to a vector when element equals target -> Option A

4. Quick Check:

   Collect all matches by looping and storing indices [OK]

Hint: Collect indices by checking all elements without breaking [OK]

Common Mistakes:

• Breaking loop too early to find all matches
• Sorting vector which changes original order
• Using hash map counts instead of indices