索引查找與分塊查找算法原理及 C 語言實現

編輯：關於C語言

基本概念

索引查找（分級查找）將主表劃分為若干子表，為每個子表建立索引項，所有索引項構成索引表。查找分兩步：先在索引表定位子表，再在子表內查找目標。

數據結構定義

typedef struct {
    IndexKeyType index;  // 索引值
    int start;           // 子表在主表中的起始下標
    int length;          // 子表長度
} IndexItem;

typedef IndexItem IndexList[ILMSize];  // 索引表
typedef ElemType MainList[MaxSize];    // 主表

索引查找算法


int Indsch(MainList A, IndexList B, int m, IndexKeyType K1, KeyType K2) {
    int i, j;
    // 1. 顺序查找索引表
    for (i = 0; i < m; i++)
        if (K1 == B[i].index) break;
    if (i == m) return -1;  // 索引值不存在
    
    // 2. 在对应子表中顺序查找
    j = B[i].start;
    while (j < B[i].start + B[i].length) {
        if (K2 == A[j].key) break;
        j++;
    }
    return (j < B[i].start + B[i].length) ? j : -1;
}

若索引值/關鍵字為字符串，改用 strcmp 比較；若子表採用鏈式存儲，將循環改為指針遍歷。

性能分析

平均查找長度 ASL = (1+m)/2 + (1+s)/2 = 1 + (m+s)/2，其中 m 為索引表長，s 為子表長。
當 s = n/m 且 m = √n 時，ASL 最小為 1+√n，時間複雜度 O(√n)。
快於順序查找 O(n)，慢於二分查找 O(log n)。

分塊查找（稀疏索引的特例）

要求：塊間有序（前塊最大關鍵字 < 後塊最小關鍵字），塊內可無序。索引值取每塊的最大關鍵字。

算法


int Blocksch(MainList A, IndexList B, int m, KeyType K) {
    int i, j;
    // 1. 顺序查找索引表，找到第一个索引值 >= K 的块
    for (i = 0; i < m; i++)
        if (K <= B[i].index) break;
    if (i == m) return -1;
    
    // 2. 在块内顺序查找
    j = B[i].start;
    while (j < B[i].start + B[i].length) {
        if (K == A[j].key) break;
        j++;
    }
    return (j < B[i].start + B[i].length) ? j : -1;
}

優化：索引表二分查找


int low = 0, high = m - 1;
while (low <= high) {
    int mid = (low + high) / 2;
    if (K == B[mid].index) { i = mid; break; }
    else if (K < B[mid].index) high = mid - 1;
    else low = mid + 1;
}
if (low > high) i = low;  // 失败时 low 指向第一个 > K 的索引
if (i == m) return -1;    // 真正查找失败