分块查找又称索引顺序查找，是顺序查找和二分查找的一种改进方法。
分块查找要求把一个数据分成若干块，每一块里面的元素可以是无序的，但对于一个递增的数组来说，第i块的最大元素一定要小于第i+1块的所有元素，分块查找还需要一个索引表，用来限定每一块的范围，在增加、删除、查找元素时都需要用到。
分块1
分块2
分块3
首先，我们看到的索引表是10、20、30，假如现在需要查找的目标值是12，通过二分查找索引表
我们可以确定12是在分块2中
然后在分块2中顺序查找，最后得到12存在于数列中。
代码如下：
#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;
}
int main()
{
int i,j=0,k;
int a[17] = {1,4,6,10,15,12,17,16,20,13,30,28,26,29,22,25};//从小到大的16个数
int key = 12;
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]; //确定每个块范围中元素的最大值
}
k=block_search(key,a); //调用函数进行查找
if(k!=0)
{
printf("查找成功，其位置是：%d ",k); //如果找到该数，则输出其下标
}
else
{
printf("查找失败!"); //若未找到，则输出提示信息
}
return 0;
}
3279916262