分塊查找
分塊查找法要求將列表組織成以下索引順序結構：
首先將列表分成若干個塊（子表）。一般情況下，塊的長度均勻，最后一塊可以不滿。
每塊中元素任意排列，即塊內無序，但塊與塊之間有序。
構造一個索引表。其中每個索引項對應一個塊并記錄每塊的起始位置，和每塊中最大
關鍵字（或最小關鍵字）。索引表按關鍵字有序排列。
下圖所示為一個索引順序表。其中包括三個塊，第一個塊的起始地址為 0，塊內最
大關鍵字為 25；第二個塊的起始地址為 5，塊內最大關鍵字為 58；第三個塊的起始地址為
10，塊內最大關鍵字為 88。
分塊查找的基本過程如下：
（1）首先，將待查關鍵字 K 與索引表中的關鍵字進行比較，以確定待查記錄所在的
塊。具體的可用順序查找法或折半查找法進行。
（2）進一步用順序查找法，在相應塊內查找關鍵字為 K的元素。
分塊查找是順序查找的一種改進方法。首先需要對數組進行分塊，分塊查找需要建立一個“索引表”。索引表分為m塊，每塊含有N/m個元素，塊內是無序的，塊間是有序的，例如塊2中最大元素小于塊3中最小元素。
先用二分查找索引表，確定需要查找的關鍵字在哪一塊，然后再在相應的塊內用順序查找。分塊查找又稱為索引順序查找。
時間復雜度：O(log(m)+N/m)
1 //分塊查找 2 template<class T>//索引表 3 struct INDEXTable 4 { 5 T key; 6 int link; 7 }; 8 9 template<class T> IndexOrderSearch(INDEXTable<T> *indexTable,T *x, int N, int m, T keyword)// indexTable為索引表,x為原數組,N為數組大小，m為塊大小 10 { 11 int L = (N+m-1)/m; 12 int i = 0; 13 while(i < L && indexTable[i].key < keyword) 14 i++; 15 if(i == L) 16 return -1; 17 else 18 { 19 int j = indexTable[i].link; 20 for(j; j<indexTable[i].link + m;j++) 21 if(x[j] == keyword) 22 return j; 23 } 24 return -1; 25 }
浙公網安備 33010602011771號