演算法筆記：四大搜尋策略完全指南（線性、二分、BST、Hash）

前言

搜尋是資料庫與 ERP 系統的核心功能。本文假設資料唯一且無重複，系統介紹四種搜尋策略：線性搜尋、二分搜尋、二元搜尋樹、雜湊表，並分析其時間複雜度與適用場景。

1. 線性搜尋

適用於無序陣列。從頭掃描至尾，找到即回傳索引，否則 -1。

int linear_search(const int array[], int length, int value)
{
    if (array == NULL || length == 0) return -1;
    for (int i = 0; i < length; ++i)
        if (array[i] == value) return i;
    return -1;
}

複雜度：最佳 O(1)、最差 O(n)、平均 O(n/2) ≈ O(n)。

2. 二分搜尋

前提：陣列已排序。每次取中間元素比較，將搜尋範圍減半。

int binary_search(const int array[], int length, int value)
{
    if (array == NULL || length == 0) return -1;
    int left = 0, right = length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);  /* 避免溢位 */
        if (array[mid] == value) return mid;
        else if (value > array[mid]) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

複雜度：O(log₂ n)。100 萬筆資料最多 20 次比較，遠優於線性搜尋。

3. 二元搜尋樹

適用於動態資料結構（指標串連），不需連續記憶體。節點定義：

typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

搜尋遞迴實作：

const Node* bst_search(const Node *root, int value)
{
    if (root == NULL) return NULL;
    if (value == root->data) return root;
    else if (value < root->data) return bst_search(root->left, value);
    else return bst_search(root->right, value);
}

複雜度：平均 O(log n)，最差 O(n)（退化成鏈表）。平衡樹（AVL、Red-Black）可保證 O(log n)。

4. 雜湊表

以雜湊函數將鍵值映射至桶索引，同桶以鏈表解決衝突。無需全域排序，適合中等規模資料。

typedef struct LinkNode {
    int data;
    struct LinkNode *next;
} LinkNode;

LinkNode* hash_search(LinkNode *buckets[], int mod, int value)
{
    int idx = value % mod;
    for (LinkNode *p = buckets[idx]; p; p = p->next)
        if (p->data == value) return p;
    return NULL;
}

複雜度：平均 O(1 + α)，α = n/mod 為負載因子。mod 越大衝突越少，但記憶體佔用增加。

策略選擇指南