线性查找 Linear Search

所谓的线性查找, 指的是从数组的一端开始, 依次遍历每一个元素, 找到目标元素后终止, 或者到达了数组的另一端才终止. 该算法还有一个别名, 叫顺序查找 sequential search.

线性查找的步骤

1. 从数组的第一个元素开始遍历整个数组
2. 将当前元素与目标元素进行比较
3. 如果当前元素与相等, 就终止循环并返回当前元素的索引值
4. 如果不相等, 就移到数组中的下一个元素
5. 重复第2-4步, 直到数组的尾部
6. 如果到达数组尾部后, 仍然没有找到想要的元素, 就返回没有找到(比如用 -1, 或者 None 表示)

线性查找的实现

#![allow(unused)]
fn main() {
#[must_use]
pub fn linear_search<T: PartialOrd>(slice: &[T], target: &T) -> Option<usize> {
    for (index, item) in slice.iter().enumerate() {
        if item == target {
            return Some(index);
        }
    }
    None
}
}

线性查找算法的特性

• 该算法的时间复杂度是 O(N), 空间复杂度是 O(1).
• 这个算法适合没有排序过的数组
• 比较适合元素较少的数组
• 不需要使用额外的内存
• 因为是依次遍历元素, CPU 缓存命中率较高