查找算法：线性查找，golang实现

前言

在实际场景中，选择合适的查找算法对于提高程序的效率和性能至关重要，本节课主要讲解"线性查找"的适用场景及代码实现。

线性查找

线性查找（Linear Search）是一种简单的查找算法，用于在一个集合（如数组或切片）中查找特定的元素。它的基本思想是逐个检查数据结构中的每个元素，直到找到所需的元素或搜索完所有数据为止。这种算法的时间复杂度为 O(n)，其中 n 是数组中的元素数量。线性查找不需要数据结构具有任何特定的顺序，因此它可以应用于任何类型的有序或无序的数据集合。然而，由于它的效率相对较低（在最坏的情况下需要遍历整个数据集），它通常不适用于大数据集或需要高效查找性能的场景。

代码示例

下面我们使用Go语言实现一个线性查找

1. 算法包

创建一个 pkg/search.go

touch pkg/search.go

2. 线性查找代码

打开 pkg/search.go 文件，代码如下

package pkg
// LinearSearch 线性查找
func LinearSearch(arr []int, target int) int {
    for k, v := range arr {
        if v == target {
            return k
        }
    }
    return -1
}

3. 模拟程序

打开 main.go 文件，代码如下：

package main
import (
    "demo/pkg"
    "fmt"
)
func main() {
    // 定义一个切片(数组)，这里我们模拟 10 个元素
    arr := []int{408, 902, 757, 859, 382, 353, 964, 473, 392, 369}
    fmt.Println("arr的长度:", len(arr))
    fmt.Println("arr的值为:", arr)
    target := 408
    index := pkg.LinearSearch(arr, target)
    if index != -1 {
        fmt.Printf("找到目标值 %d , 在索引 %d \n", target, index)
    } else {
        fmt.Printf("没有找到目标值 %d \n", target)
    }
}

4. 运行程序

go run main.go

在我们定义的切片（数组）第一个就是我们的目标值：408

所以在 if 判断里，index 不等于 -1，输出：找到了 408 这个目标值，在切片（数组）中的索引为 0

循环次数

以上代码中，我们使用了 for 循环来查找目标值是否存在，根据 线性查找的查找方式，如果我们的目标值是 369（最后一位），或是不存在这个切片（数组）中，又会如何呢？

我们来做个测试，实践得真理！

假如目标值正好在数组中的第一位

循环次数 1 次

假如目标值正好在数组中的第五位

循环次数 5 次

假如目标值正好在数组中的最后一位

循环次数 10 次

假如目标值不在数组中

循环次数 10 次

线性查找的思想

1. 顺序遍历

从数据结构的开始（通常是索引 0 ）按顺序遍历到结束。所以上面的循环中，目标值在第一位时，就只遍历一次，在第五位时，遍历五次，以此类推，而如果找不到目标值时，就会遍历整个数组的长度

2. 比较

在遍历过程中，将当前元素与目标值进行比较

3. 返回结果

• 如果找到目标值，则返回该元素在数据结构中的索引
• 如果遍历完整个数据结构都没有找到目标值，则返回一个表示未找到的值（通常是 -1 ）

线性查找的适用场景

1. 数据量小

当需要搜索的数据集非常小时，线性查找的简单性可能使其成为一个合理的选择，即使它的效率不是最高的

2. 未排序的数据

如果数据未排序，则使用更高效的查找算法（如二分查找）是不适用的，因为二分查找要求数据已排序

3. 几乎不重复的数据

如果数据集中每个元素几乎都不相同，且数据规模不大，那么线性查找的效率损失可能是可以接受的

4. 数据频繁变更

如果数据集频繁更改（例如，元素经常被添加或删除），那么维护排序可能会很昂贵，此时线性查找可能是一个更简单的选择

5. 缓存未命中

在某些情况下，如果数据存储在外部存储（如硬盘）中，并且数据访问模式导致缓存未命中率高，那么线性查找的额外计算开销可能不是主要瓶颈，而数据访问的延迟可能更重要