## Linear Search in Rust, Python

### How to search an element in a list? How to implement Linear Search in Rust?

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:

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:

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):

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.