7.2.3 分块查找

分块查找把表分成块，块间有序、块内可无序。索引保存每块最大关键字与起点；先在索引定位块，再在块内顺序查找。它在更新灵活性与查找速度间折中。

手工推演

块1[3,1,5]最大5，块2[9,7,8]最大9，块3[14,11]最大14。查7先在索引找到块2，再块内比较9、7。

结构与代码

若n项均匀分b块，索引顺序查约(b+1)/2次，块内约(n/b+1)/2次；数量级在b约等于sqrt(n)时平衡。索引也可折半。

正确性

块间有序保证目标只可能落在首个最大值不小于x的块；块内扫描保证不遗漏。

错解反馈

要求块内也有序；索引最大值未随插入更新；越界插入破坏块间范围。

迁移训练

n=100，索引与块内都顺序查，块数约取多少？答案约10。