数据结构索引分块查找刷题

Question

设顺序存储的线性表共有l00个元素，按分块查找(索引查找)的要求等分成5块。若对索引表采用二分查找来确定块，并在确定的块中进行顺序查找，则在概率相等的情况下，分块查找成功时的平均查找长度是多少(要求利甩∑P i C i 来计算并给出详细算式)?

答案是：

请问对索引表的查找为什么是图中的算法? 为什么是1*1+2*2+2*3 ?在网上没找到这个公式啊

Answer 1

a b c d e

二分查找

找到 c 需要比较 1 次（二分，从中间开始比较）
找到 a,d 需要 2 次（先跟 c 比，根据结果剩余的区间二分，偶数个元素假设先跟小的比）
找到 b,e 需要 3 次（c->a->b 或 c->d->e）

所以是 1*1 + 2*2 + 3*2。