目錄

前言

線性查找

代碼示例

1. 算法包

2. 線性查找代碼

3. 模擬程序

4. 運行程序

循環(huán)次數(shù)

假如目標值正好在數(shù)組中的第一位

假如目標值正好在數(shù)組中的第五位

假如目標值正好在數(shù)組中的最后一位

假如目標值不在數(shù)組中

線性查找的思想

1. 順序遍歷

2. 比較

3. 返回結果

線性查找的適用場景

1. 數(shù)據(jù)量小

2. 未排序的數(shù)據(jù)

3. 幾乎不重復的數(shù)據(jù)

4. 數(shù)據(jù)頻繁變更

5. 緩存未命中

---

前言

在實際場景中，選擇合適的查找算法對于提高程序的效率和性能至關重要，本節(jié)課主要講解"線性查找"的適用場景及代碼實現(xiàn)。

線性查找

線性查找（Linear Search）是一種簡單的查找算法，用于在一個集合（如數(shù)組或切片）中查找特定的元素。它的基本思想是逐個檢查數(shù)據(jù)結構中的每個元素，直到找到所需的元素或搜索完所有數(shù)據(jù)為止。這種算法的時間復雜度為 O(n)，其中 n 是數(shù)組中的元素數(shù)量。線性查找不需要數(shù)據(jù)結構具有任何特定的順序，因此它可以應用于任何類型的有序或無序的數(shù)據(jù)集合。然而，由于它的效率相對較低（在最壞的情況下需要遍歷整個數(shù)據(jù)集），它通常不適用于大數(shù)據(jù)集或需要高效查找性能的場景。

代碼示例

下面我們使用Go語言實現(xiàn)一個線性查找

1. 算法包

創(chuàng)建一個 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/pkg""fmt"
)func main() {// 定義一個切片(數(shù)組)，這里我們模擬 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

在我們定義的切片（數(shù)組）第一個就是我們的目標值：408

所以在 if 判斷里，index 不等于 -1，輸出：找到了 408 這個目標值，在切片（數(shù)組）中的索引為 0

循環(huán)次數(shù)

以上代碼中，我們使用了 for 循環(huán)來查找目標值是否存在，根據(jù) 線性查找的查找方式，如果我們的目標值是 369（最后一位），或是不存在這個切片（數(shù)組）中，又會如何呢？

我們來做個測試，實踐得真理！

假如目標值正好在數(shù)組中的第一位

循環(huán)次數(shù) 1 次

假如目標值正好在數(shù)組中的第五位

循環(huán)次數(shù) 5 次

假如目標值正好在數(shù)組中的最后一位

循環(huán)次數(shù) 10 次

假如目標值不在數(shù)組中

循環(huán)次數(shù) 10 次

線性查找的思想

1. 順序遍歷

從數(shù)據(jù)結構的開始（通常是索引 0 ）按順序遍歷到結束。所以上面的循環(huán)中，目標值在第一位時，就只遍歷一次，在第五位時，遍歷五次，以此類推，而如果找不到目標值時，就會遍歷整個數(shù)組的長度

2. 比較

在遍歷過程中，將當前元素與目標值進行比較

3. 返回結果

• 如果找到目標值，則返回該元素在數(shù)據(jù)結構中的索引
• 如果遍歷完整個數(shù)據(jù)結構都沒有找到目標值，則返回一個表示未找到的值（通常是 -1 ）

線性查找的適用場景

1. 數(shù)據(jù)量小

當需要搜索的數(shù)據(jù)集非常小時，線性查找的簡單性可能使其成為一個合理的選擇，即使它的效率不是最高的

2. 未排序的數(shù)據(jù)

如果數(shù)據(jù)未排序，則使用更高效的查找算法（如二分查找）是不適用的，因為二分查找要求數(shù)據(jù)已排序

3. 幾乎不重復的數(shù)據(jù)

如果數(shù)據(jù)集中每個元素幾乎都不相同，且數(shù)據(jù)規(guī)模不大，那么線性查找的效率損失可能是可以接受的

4. 數(shù)據(jù)頻繁變更

如果數(shù)據(jù)集頻繁更改（例如，元素經(jīng)常被添加或刪除），那么維護排序可能會很昂貴，此時線性查找可能是一個更簡單的選擇

5. 緩存未命中

在某些情況下，如果數(shù)據(jù)存儲在外部存儲（如硬盤）中，并且數(shù)據(jù)訪問模式導致緩存未命中率高，那么線性查找的額外計算開銷可能不是主要瓶頸，而數(shù)據(jù)訪問的延遲可能更重要