Linear Search is exactly what it sounds like. You traverse the list linearly, searching for the element you are looking for.

Approach

• Compare each element with the element you are searching starting from the leftmost element (0th index of list)
• If the element matches, return the index of the element it matched with
• Else keep looking in the list, and if not found return -1, since -1 generally denotes an invalid index (in Rust use None, see code below).

Complexity

Since the element can be anywhere in the list, the maximum time to find this element will be same as the time required to traverse the list ie linear time.

O(n), where n is this number of elements in the list

Implementation in Rust

Linear Search Function

This is fairly easy to implement, lets look at the code below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

fn search<T>(list: &Vec<T>, element: &T) -> Option<usize>
where
    T: PartialOrd,
{
    for (pos, e) in list.iter().enumerate() {
        if e == element {
            return Some(pos);
        }
    }
    return None;
}

Running tests

Below is the complete program with test cases:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

fn search<T>(list: &Vec<T>, element: &T) -> Option<usize>
where
    T: PartialOrd,
{
    for (pos, e) in list.iter().enumerate() {
        if e == element {
            return Some(pos);
        }
    }
    return None;
}

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

    #[test]
    fn test_search_success_found() {
        let example_list: Vec<i32> = vec![2, 41, 1, 65, 7, 8, 54];
        assert_eq!(search(&example_list, &7), Some(4));
    }

    #[test]
    fn test_search_success_not_found() {
        let example_list: Vec<i32> = vec![2, 41, 1, 65, 7, 8, 54];
        assert_eq!(search(&example_list, &20), None);
    }
}

Run following to run the tests (remove --test to run the code):

1

rustc linear-search.rs --test; ./linear-search

More

Check out this Visualization and Wiki Link for more details.

Note: You could be searching for first/last/multiple occurrence of the element, these are nuances and can be handled in your code respectively.