Linear Search

Linear search is the simplest searching algorithm. It works by checking each element in a collection one by one until the target value is found or the end of the list is reached. Because it makes no assumptions about data order, linear search works on both sorted and unsorted datasets.

While not the fastest method for large inputs, linear search is an essential starting point for understanding how searching algorithms work.

Example Walk-through

Consider this array:

[3, 7, 2, 9, 5]

We want to search for the value 9.

Step-by-step search

• Compare 3 with 9 → not a match
• Compare 7 with 9 → not a match
• Compare 2 with 9 → not a match
• Compare 9 with 9 → match found

The search stops immediately when the target value is found.

If the value does not exist in the array, linear search continues until all elements are checked.

Rust Implementation

This implementation scans the slice sequentially and returns the index of the target if found.

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

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_finds_existing_element() {
        let input = vec![3, 7, 2, 9, 5];
        assert_eq!(linear_search(&input, 9), Some(3));
    }

    #[test]
    fn it_returns_none_for_missing_element() {
        let input = vec![3, 7, 2, 9, 5];
        assert_eq!(linear_search(&input, 4), None);
    }
}

Example Usage

fn main() {
    let values = vec![10, 23, 45, 70, 11, 15];
    let target = 70;

    match linear_search(&values, target) {
        Some(index) => println!("Found {} at index {}", target, index),
        None => println!("{} not found", target),
    }
}

Time and Space Complexity

Linear search examines elements sequentially, so performance depends on where the target appears.

Space Complexity

When to Use Linear Search

Linear search is useful when:

• The data is unsorted
• The dataset is small
• Simplicity matters more than performance
• Only a single lookup is required

For large datasets or repeated searches, more efficient algorithms such as binary search are preferred.

Playground Links

Rust - Linear Search