分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

方法描述：将n个数据元素"按块有序"划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须"按块有序"；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。

操作步骤：

step1 先选取各块中的最大关键字构成一个索引表；

step2 查找分两个部分：先对索引表进行二分查找或

顺序查找，以确定待查记录在哪一块中；

然后，在已确定的块中用顺序法进行查找。

在C语言中：

#include <stdio.h>

struct index /*定义块的结构*/

{

int key;

int start;

int end;

} index_table[4]; /*定义结构体数组*/

int block_search(int key, int a[]) /*自定义实现分块查找*/

{

int i, j;

i = 1;

while (i <= 3 && key > index_table[i].key) /*确定在那个块中*/

i++;

if (i > 3) /*大于分得的块数，则返回0*/

return 0;

j = index_table[i].start; /*j等于块范围的起始值*/

while (j <= index_table[i].end && a[j] != key) /*在确定的块内进行查找*/

j++;

if (j > index_table[i].end) /*如果大于块范围的结束值，则说明没有要查找的数,j置0*/

j = 0;

return j;

}

main()

{

int i, j = 0, k, key, a[16];

printf("please input the number:\");

for (i = 1; i < 16; i++)

scanf("%d", &a[i]); /*输入由小到大的15个数*/

for (i = 1; i <= 3; i++)

{

index_table[i].start = j + 1; /*确定每个块范围的起始值*/

j = j + 1;

index_table[i].end = j + 4; /*确定每个块范围的结束值*/

j = j + 4;

index_table[i].key = a[j]; /*确定每个块范围中元素的最大值*/

}

printf("please input the number which do you want to search:\");

scanf("%d", &key); /*输入要查询的数值*/

k = block_search(key, a); /*调用函数进行查找*/

if (k != 0)

printf("success.the position is :%d\", k); /*如果找到该数，则输出其位置*/

else

printf("no found!"); /*若未找到则输出提示信息*/

}

平均查找长度

设表共n个结点，分b块，s=n/b

(二分查找索引表)平均查找长度=Log2（n/s+1）+s/2

(顺序查找索引表)平均查找长度=(s*s+2s+n)/(2s)