分块查找也称为顺序查找,要求将待查的元素均匀的分成块,块间按大小排序,块内不排序,所以要建立一个块的最大或最小关键字表,称为索引表

#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) return 0;
        j = index_table[i].start;
        while(j <= index_table[i].end && a[j] != key){
                j++;
        }
        if(j>index_table[i].end) j = 0;
        return j;
}

void main()
{
        int i,j=0,k,key,a[16];
        for(i=1;i<16;i++)
                a[i] = i;
        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];
        }

        scanf("%d",&key);
        k = block_search(key,a);
        printf("%d",k);
}