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

分块查找要求把一个数据分成若干块，每一块里面的元素可以是无序的，但对于一个递增的数组来说，第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\n",k);    //如果找到该数，则输出其下标

    }

    else

    {

        printf("查找失败!");    //若未找到，则输出提示信息

    }

    return 0;

}