分块查找

分块查找：又称索引顺序查找，其查找性能介于折半查找和顺序查找之间

分块查找的使用前提是将线性表进行分块，并使其分块有序，所谓分块有序是指将线性表划分为若干块，每一块内不要求有序(即块内无序)，但要求第二块中所有记录的关键码均大于第一块中所有记录的关键码，第三块中所有记录的关键码均大于第二块中所有记录的关键码，以此类推(即块间有序)

分块查找还需要建立一个索引表，每块对应一个索引项，各索引项按关键码有序排序

分块查找需要分两步进行：第一步在索引表中确定待查关键码所在的块；第二步在相应块中查找待查关键码。由于索引表是按关键码有序排列，可使用顺序查找，也可使用折半查找；在块内进行查找时，由于块内是无序的，只能使用顺序查找