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

目录

前言

线性查找

代码示例

1. 算法包

2. 线性查找代码

3. 模拟程序

4. 运行程序

循环次数

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

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

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

假如目标值不在数组中

线性查找的思想

1. 顺序遍历

2. 比较

3. 返回结果

线性查找的适用场景

1. 数据量小

2. 未排序的数据

3. 几乎不重复的数据

4. 数据频繁变更

5. 缓存未命中

---

前言

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

线性查找

线性查找（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. 缓存未命中

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