1. 基本概念

線性搜索（Linear Search），也稱為順序搜索，是一種在列表中查找特定元素的算法。它從列表的第一個(gè)元素開(kāi)始，逐個(gè)檢查每個(gè)元素，直到找到目標(biāo)元素或檢查完所有元素。

2. 工作原理

線性搜索的操作過(guò)程如下：

1. 初始化：從列表或數(shù)組的第一個(gè)元素開(kāi)始。

2. 遍歷元素：按順序訪問(wèn)每個(gè)元素。

3. 比較：將當(dāng)前元素與目標(biāo)值進(jìn)行比較。

4. 匹配檢查：

   • 如果當(dāng)前元素等于目標(biāo)值，則返回當(dāng)前索引（即位置）。
   • 如果當(dāng)前元素不等于目標(biāo)值，則繼續(xù)檢查下一個(gè)元素。

5. 結(jié)束條件：

   • 如果找到目標(biāo)值，返回其索引。
   • 如果遍歷完所有元素后未找到目標(biāo)值，返回一個(gè)表示未找到的標(biāo)志（通常是 -1）。

3. 算法步驟

以下是線性搜索的詳細(xì)步驟：

1. 輸入：

   • 一個(gè)列表或數(shù)組 arr。
   • 一個(gè)目標(biāo)值 target。

2. 步驟：

   • 初始化索引 i 為 0。
   • 進(jìn)入循環(huán)，直到 i 小于 arr.length。
     • 如果 arr[i] 等于 target，則返回 i。
     • 否則，增加 i，繼續(xù)檢查下一個(gè)元素。
   • 如果循環(huán)結(jié)束后仍未找到目標(biāo)值，返回 -1。

4. 時(shí)間復(fù)雜度分析

• 最壞情況：
  • 當(dāng)目標(biāo)值不在數(shù)組中時(shí)，需要檢查所有 n 個(gè)元素，時(shí)間復(fù)雜度為 O(n)。
• 最佳情況：
  • 當(dāng)目標(biāo)值是第一個(gè)元素時(shí)，只需檢查一次，時(shí)間復(fù)雜度為 O(1)。
• 平均情況：
  • 通常需要檢查一半的元素，時(shí)間復(fù)雜度為 O(n)，假設(shè)目標(biāo)值均勻分布。

5. 空間復(fù)雜度

• 空間復(fù)雜度：線性搜索只需要少量的額外存儲(chǔ)空間來(lái)存儲(chǔ)索引變量，因此空間復(fù)雜度為 O(1)。

6. 實(shí)現(xiàn)代碼

public class LinearSearch {/*** 執(zhí)行線性搜索* @param arr 要搜索的數(shù)組* @param target 目標(biāo)值* @return 目標(biāo)值的索引，如果未找到返回-1*/public static int linearSearch(int[] arr, int target) {// 遍歷數(shù)組中的每一個(gè)元素for (int i = 0; i < arr.length; i++) {// 比較當(dāng)前元素和目標(biāo)值if (arr[i] == target) {// 找到目標(biāo)值，返回索引return i;}}// 遍歷完所有元素后，未找到目標(biāo)值return -1;}public static void main(String[] args) {// 示例數(shù)組int[] numbers = {4, 2, 7, 1, 9, 3};// 目標(biāo)值int target = 7;// 執(zhí)行線性搜索int result = linearSearch(numbers, target);// 輸出搜索結(jié)果if (result != -1) {System.out.println("元素 " + target + " 在數(shù)組中的索引是: " + result);} else {System.out.println("元素 " + target + " 不在數(shù)組中。");}}
}

代碼解讀：

• public static int linearSearch(int[] arr, int target)：

  • 定義了一個(gè)靜態(tài)方法 linearSearch，接受兩個(gè)參數(shù)：一個(gè)整數(shù)數(shù)組 arr 和一個(gè)目標(biāo)值 target。
  • 方法返回目標(biāo)值的索引，如果未找到則返回 -1。

• for (int i = 0; i < arr.length; i++)：

  • 使用 for 循環(huán)遍歷數(shù)組 arr 的每個(gè)元素。
  • i 從 0 開(kāi)始，到 arr.length - 1 結(jié)束。

• if (arr[i] == target)：

  • 在每次循環(huán)中，檢查當(dāng)前元素 arr[i] 是否等于目標(biāo)值 target。
  • 如果相等，返回當(dāng)前索引 i。

• return -1：

  • 如果循環(huán)結(jié)束后仍未找到目標(biāo)值，則返回 -1，表示目標(biāo)值不在數(shù)組中。

• public static void main(String[] args)：

  • main 方法是程序的入口點(diǎn)，定義了一個(gè)示例數(shù)組 numbers 和一個(gè)目標(biāo)值 target。
  • 調(diào)用 linearSearch 方法，獲取搜索結(jié)果并輸出。

7. 實(shí)際應(yīng)用

• 小型數(shù)據(jù)集：當(dāng)數(shù)據(jù)量較小時(shí)，線性搜索簡(jiǎn)單有效。
• 無(wú)序數(shù)據(jù)：對(duì)于無(wú)序數(shù)據(jù)，線性搜索不需要排序即可查找目標(biāo)元素。
• 偶爾查詢：在需要偶爾執(zhí)行搜索操作時(shí)，線性搜索足夠且易于實(shí)現(xiàn)。

8. 變體和改進(jìn)

• 雙向搜索：在一些特殊情況下，可以從數(shù)組的兩端同時(shí)進(jìn)行搜索，可能會(huì)提高效率。
• 跳表（Jump Search）：在某些應(yīng)用場(chǎng)景中，對(duì)線性搜索進(jìn)行改進(jìn)，提高搜索效率。
• 哈希表：對(duì)需要頻繁查找的場(chǎng)景，可以使用哈希表來(lái)優(yōu)化搜索時(shí)間。