高校问答猫只有一边胡子:什么是分块查找法
来源：百度文库 编辑：高校问答 时间：2024/05/02 20:30:51
分块查找又索引查找，它主要用于“分块有序”表的查找。所谓“分块有序”是指将线性表L（一维数组）分成m个子表（要求每个子表的长度相等），且第i+1个子表中的每一个项目均大于第i个子表中的所有项目。“分块有序”表应该包括线性表L本身和分块的索引表A。因此，分块查找的关键在于建立索引表A。
（1）建立索引表A（二维数组）
索引表包括两部分：关键字项（子表中的最大值）和指针项（子表的第一项在线性表L中位置）
索引表按关键字有序的。
例如：线性表L（有序）为：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3个子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二维数组：第一列为每个子表的最大值 ，第二列为每个子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，确定待查项X所在的子表（块）。
（3）在所确定的子表中可以用“折半查找”法搜索待查项X；若找到则输出X；否则输出未找到信息。
我不懂，谁能给我解释一下，最好有例题分析
（1）建立索引表A（二维数组）
索引表包括两部分：关键字项（子表中的最大值）和指针项（子表的第一项在线性表L中位置）
索引表按关键字有序的。
例如：线性表L（有序）为：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3个子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二维数组：第一列为每个子表的最大值 ，第二列为每个子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，确定待查项X所在的子表（块）。
（3）在所确定的子表中可以用“折半查找”法搜索待查项X；若找到则输出X；否则输出未找到信息。
我不懂，谁能给我解释一下，最好有例题分析