查找算法全景指南：從線性掃描到哈希表的時間空間權衡藝術

前言

查找是計算機科學中最基礎、最高頻的操作之一。無論是數據庫索引、編譯器符號表、緩存系統還是業務代碼中的 Map 查詢，核心都在於如何在數據集合中高效定位目標。本文系統梳理四大經典查找範式——順序查找、二分查找、二叉搜索樹、哈希表，從原理、代碼實現、複雜度分析到工程選型，構建完整知識體系。

一、順序查找：最樸素的暴力美學

適用場景：無序數據、極小規模 (n < 50)、單次查詢、數據流流式處理。

int linear_search(const int arr[], int len, int target) {
    if (!arr || len <= 0) return -1;
    for (int i = 0; i < len; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

二、二分查找：有序數組的對數級加速器

核心前提：數組必須有序（升序或降序）。

關鍵技巧：mid = left + ((right - left) >> 1) 防止 left + right 溢出；循環條件 left <= right 確保單元素區間被檢查。

int binary_search(const int arr[], int len, int target) {
    if (!arr || len <= 0) return -1;
    int left = 0, right = len - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

工程陷阱：頻繁插入/刪除導致維護有序數組代價高昂 (O(n) 移動)，此時優先考慮平衡樹或跳表。

三、二叉搜索樹 (BST)：動態有序集合的指針實現

定義：對任意節點，左子樹鍵值 < 節點鍵值 < 右子樹鍵值。

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

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

生產級選型：紅黑樹 (RB-Tree) / AVL 樹 / B+ 樹 — 自平衡保證 O(log n) 最壯界，是 std::map、MySQL InnoDB 索引、Linux 虛擬內存區管理的底層結構。

四、哈希表：O(1) 期望查找的工程基石

核心思想：索引 = Hash(Key) % TableSize，將鍵映射到桶，桶內用鏈表/開放寬址解決衝突。

typedef struct HashNode {
    int key;
    struct HashNode *next;
} HashNode;

HashNode* hash_search(HashNode* buckets[], int mod, int key) {
    int idx = key % mod;
    HashNode* cur = buckets[idx];
    while (cur) {
        if (cur->key == key) return cur;
        cur = cur->next;
    }
    return NULL;
}

工程必知：

• 哈希函數質量：決定分布均勻度，推薦 xxHash、MurmurHash。
• 擴容策略：負載因子超閾值 (如 0.75) 觸發 2x 擴容 + Rehash，增量式避免卡頓。
• 衝突解決：鏈表法簡單通用；開放寬址 (線性探測/雙重哈希) 緊湊緩存友好，但刪除複雜需懶惰標記。

五、綜合選型決策表

結語

查找算法沒有銀彈，只有基於數據特徵、訪問模式、硬體約束的工程權衡。掌握四大範式的核心機制與邊界條件，才能在架構設計與性能調優中遊刃有餘。下一篇將進入排序算法領域，探討如何將「無序」轉化為「有序」的計算藝術。