数据结构复习资料
例 如 ， 给 定 关 键 字 序 列 如 下 ： 22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53, 假 设 n=3,即将该序列分成3个子表，每个子表有6个元素，则 得到的主表和索引表如图所 示。22 0 48 6 86 12
22 12 13 8
9
20 33 42 44 38 24 48 60 58 74 49 86 53
分块查找的过程是先确定待查记录所在的块，然后在块中 顺序查找。假设给定k=38, 则先在索引表中按顺序比较，因为 22<k<48,则可确定38应该在第二块中，从第二块的第一个记 录 array[6] 顺序查起. 分块查找的时间复杂度是O(m+n) m是块长度，n是索引表 长度。