常用查找算法全解析：從順序查找到哈希查找

編輯：關於C語言

常用查找算法全解析

查找算法是計算機科學中的基石，廣泛應用於數據庫索引、搜尋引擎、編譯器符號表等場景。本文系統總結五大經典查找算法，涵蓋原理、複雜度、適用場景及 C 語言實現，助你快速掌握核心技術。

1. 順序查找（Sequential Search）

時間複雜度： O(n)
優點： 算法簡單，對數據無序無要求。
缺點： 效率低，僅適合小數據量。
適用場景： 數據量較少、無序或頻繁插入刪除的線性表。

核心原理： 從線性表一端開始，將關鍵字與每個元素逐一比對，直到找到匹配或遍歷結束。

基礎版實現：

int SequenceSearch(int *array, int size, int key) {
    int i;
    for (i = 0; i < size; i++) {
        if (array[i] == key) return i;
    }
    return -1;
}

哨兵優化版（減少邊界判斷）：

int SequenceSearch(int *array, int size, int key) {
    int i = size - 1;
    array[0] = key; // 設置哨兵
    while (key != array[i]) i--;
    return i; // 返回 0 表示查找失敗
}

2. 二分查找 / 折半查找（Binary Search）

時間複雜度： O(log n)
優點： 比較次數少，速度快，平均性能優。
缺點： 要求有序表，插入刪除困難。
適用場景： 不常變動、查找頻繁的有序列表。

核心原理： 利用中間元素將有序表劃分為兩個子表，根據關鍵字與中間值大小關係縮小查找範圍，重複直至找到或子表為空。

int BinarySearch(int *array, int size, int key) {
    int first = 0, last = size - 1, middle;
    while (first <= last) {
        middle = (first + last) / 2;
        if (array[middle] < key) first = middle + 1;
        else if (array[middle] > key) last = middle - 1;
        else return middle;
    }
    return -1;
}

3. 插值查找（Interpolation Search）

時間複雜度： O(log n)（數據均勻時接近 O(log log n)）
適用場景： 數據量大且關鍵字分布均勻的有序表。

核心原理： 模擬查字典動作，根據關鍵字在數據範圍中的比例預估位置，而非固定取中間。公式：pos = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low])。

int InsertSearch(int *array, int size, int key) {
    int first = 0, last = size - 1, position;
    while (first <= last) {
        position = first + (last - first) * (key - array[first]) / (array[last] - array[first]);
        if (array[position] < key) first = position + 1;
        else if (array[position] > key) last = position - 1;
        else return position;
    }
    return -1;
}

4. 斐波那契查找（Fibonacci Search）

時間複雜度： O(log n)
優點： 平均性能優於折半查找，僅涉及加減運算。
缺點： 要求表長 n 滿足 n = F[k] - 1（F 為斐波那契數），需補齊元素。
適用場景： 靜態有序表，且希望減少除法運算的場景。

核心原理： 利用斐波那契數列特性劃分查找區間，每次比較後縮小範圍至 F[k-1] 或 F[k-2] 大小。

int FibonacciSearch(int *a, int n, int key) {
    int F[100], low = 1, high = n, mid, k = 0, i;
    F[0] = 0; F[1] = 1;
    for (i = 2; i < 100; i++) F[i] = F[i-1] + F[i-2];
    while (n > F[k] - 1) k++;
    for (i = n; i < F[k] - 1; i++) a[i] = a[n]; // 補齊
    while (low <= high) {
        mid = low + F[k-1] - 1;
        if (key < a[mid]) { high = mid - 1; k--; }
        else if (key > a[mid]) { low = mid + 1; k -= 2; }
        else return (mid <= n) ? mid : n;
    }
    return -1;
}

5. 哈希查找（Hash Search）

時間複雜度： O(1) 平均情況
優點： 查找速度極快，不依賴數據順序。
缺點： 需處理衝突，空間換時間，不適合範圍查詢。
適用場景： 海量數據精確匹配、關聯數組、緩存系統。

核心原理： 通過哈希函數將關鍵字映射為存儲地址，常用除留餘數法。衝突解決採用開放定址法（線性探測）。

#define HASHSIZE 12
#define NULLKEY -32768
typedef struct { int *elem; int count; } HashTable;

int Hash(int key) { return key % HASHSIZE; }

void InsertHash(HashTable *H, int key) {
    int addr = Hash(key);
    while (H->elem[addr] != NULLKEY) addr = (addr + 1) % HASHSIZE;
    H->elem[addr] = key;
}

int SearchHash(HashTable H, int key, int *addr) {
    *addr = Hash(key);
    while (H.elem[*addr] != key) {
        *addr = (*addr + 1) % HASHSIZE;
        if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) return 0;
    }
    return 1;
}

總結與選型建議

算法	時間複雜度	數據要求	推薦場景
順序查找	O(n)	無序/少量	小規模、動態數據
二分查找	O(log n)	有序、靜態	通用高效查找
插值查找	O(log n)	有序、均勻	大量均勻分佈數據
斐波那契查找	O(log n)	有序、特定長度	避免除法、靜態表
哈希查找	O(1)	無序、可哈希	海量精確匹配、緩存