线性搜索

alt text

From Wikipedia: linear search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched. Linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list.

Properties

  • Worst case performance O(n)
  • Best case performance O(1)
  • Average case performance O(n)
  • Worst case space complexity O(1) iterative
  1. use std::cmp::PartialEq;
  3. pub fn linear_search<T: PartialEq>(item: &T, arr: &[T]) -> Option<usize> {
  4.     for (i, data) in arr.iter().enumerate() {
  5.         if item == data {
  6.             return Some(i);
  7.         }
  8.     }
  10.     None
  11. }
  13. #[cfg(test)]
  14. mod tests {
  15.     use super::*;
  17.     #[test]
  18.     fn search_strings() {
  19.         let index = linear_search(&"a", &vec!["a", "b", "c", "d", "google", "zoo"]);
  20.         assert_eq!(index, Some(0));
  21.     }
  23.     #[test]
  24.     fn search_ints() {
  25.         let index = linear_search(&4, &vec![1, 2, 3, 4]);
  26.         assert_eq!(index, Some(3));
  28.         let index = linear_search(&3, &vec![1, 2, 3, 4]);
  29.         assert_eq!(index, Some(2));
  31.         let index = linear_search(&2, &vec![1, 2, 3, 4]);
  32.         assert_eq!(index, Some(1));
  34.         let index = linear_search(&1, &vec![1, 2, 3, 4]);
  35.         assert_eq!(index, Some(0));
  36.     }
  38.     #[test]
  39.     fn not_found() {
  40.         let index = linear_search(&5, &vec![1, 2, 3, 4]);
  41.         assert_eq!(index, None);
  42.     }
  44.     #[test]
  45.     fn empty() {
  46.         let index = linear_search(&1, &vec![]);
  47.         assert_eq!(index, None);
  48.     }
  49. }