# 分块查找 分块查找在线性表基础上建立一个索引层，此索引层的每个节点代表线性表的一“块”，如5个元素一块。块间是有序的，即索引层第1个节点所包揽的5个元素，必须全部小于索引层第2个节点所包揽的5个元素里的每一个，以此类推。而块内的各个元素不需要有序。每块大小可以一致，也可以不同，数据结构考试中一般默认大小一致。 分块查找索引表的构建分两步，①根据已有线性表构造分块查找索引；②动态增删元素时加入对应索引。数据结构考试中一般只关注第①步（纯理论理想情况），实际工作中一般多考虑第②步。 如图所示，每5个元素一块，以5个元素中的**最大值作为索引值**。  查找时，先对索引表进行查找，因为索引表有序，所以既可以顺序查找，也可以二分查找。找到**第一个不小于被查值**的索引节点，进入其块内，再进行顺序查找。 ## 总结和拓展 - 使用已有线性表构造分块查找索引时，对线性表是有要求的，要求“块间有序，块内可以无序”，而不是“整体都可以无序”。数据结构考题中一般会默认它给出的线性表满足条件。实际工作中，为了达成这样的条件，可以考虑直接使用有序表（反正只构建一次），也可以考虑一种快速排序的拓展形式——多标兵、多指针的元素比较和交换，以此来实现多块间有序。 - 分块查找是一种与归并排序一样，适合数据不能一次性全放入内存的情景的算法，只不过一个是查找，一个是排序。 - 分块查找是介于“有序表二分查找”和“任意表顺序查找”这两种算法间的一种折衷，对线性表本身格式的要求减少了一些，也没有顺序查找那种程度的性能损失。