順序查找：線性掃描基礎與 C 語言哨兵優化實現

核心思想：最樸素的查找

順序查找又稱線性查找。從表頭（或表尾）開始，逐個比較記錄關鍵字與給定值，相等則成功返回位置；遍歷完畢仍未找到則失敗。無需數據有序、無需特定存儲結構，是最通用但效率最低的查找方式。

基本流程

1. 設置索引 i = 0（或 n-1）。
2. 迴圈 i < n：比較 arr[i] == key。
3. 相等 → 返回 i；不等 → i++ 繼續。
4. 迴圈結束 → 返回 -1 表示失敗。

C 語言基本實現

#include <stdio.h>
#include <stdlib.h>

int arr[10] = {9, 5, 8, 3, 2, 7, 4, 0, 6, 1};

int SequentialSearch(int *a, int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key) return i;
    return -1;
}

int main() {
    int key = 2;
    int pos = SequentialSearch(arr, 10, key);
    if (pos == -1) printf("查找失敗\n");
    else { printf("查找成功\n位置：%d\n", pos); }
    return 0;
}

哨兵優化：消除邊界判斷

基本版每輪迴圈需判斷 i < n（邊界）與 a[i] == key（匹配）兩次條件。引入哨兵：在陣列第 0 位（或擴展位）預存 key，從表尾向前掃描，僅判斷 a[i] != key，必定在哨兵處停止，再檢查 i == 0 區分成功/失敗。

哨兵優化實現

int SequentialSearch_Sentinel(int *a, int n, int key) {
    a[0] = key;                    // 0 位作哨兵，原數據從 1 開始存
    int i = n;
    while (a[i] != key) i--;       // 單一判斷，必定終止
    return i;                      // i==0 失敗，i>0 成功位置
}

效能特性對比

總結

順序查找是查找算法的「Hello World」，雖時間複雜度線性，但理解其哨兵優化思想（以空間/修改數據換時間、消除邊界檢查）對後續學習哈希表槽位設計、字串匹配 KMP 失敗函數等進階技巧極具啟發意義。工程上，小規模（<50）、無序、單次查找場景仍可直接使用。