贷款 东莞网站建设,做网站毕业设计存在的问题,移动网站设计教程,网站建设2000元目录
前言
线性查找
代码示例
1. 算法包
2. 线性查找代码
3. 模拟程序
4. 运行程序
循环次数
假如目标值正好在数组中的第一位
假如目标值正好在数组中的第五位
假如目标值正好在数组中的最后一位
假如目标值不在数组中
线性查找的思想
1. 顺序遍历
2. 比较
3.…
目录
前言
线性查找
代码示例
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 mainimport (demo/pkgfmt
)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 : 408index : 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. 缓存未命中
在某些情况下如果数据存储在外部存储如硬盘中并且数据访问模式导致缓存未命中率高那么线性查找的额外计算开销可能不是主要瓶颈而数据访问的延迟可能更重要
