【数据结构】分块查找

2.源数据表

3.示例代码

#include <stdio.h>
typedef struct
{
    int max;//每一块的最大值
    int post;//每一块的起始下标
}index_t;
int findByBlock(int* a, int n1, index_t* b, int n2, int x)
{
    int start,end;//用来保存块的起始和终止下标
    //1.先确定x可能在哪一块中
    int i;
    for(i = 0; i < n2; i++)
    {
        if(x <= b[i].max)//说明可能在b[i]块中
            break;
    }
    if(i == n2)//说明没有执行过break,说明x,比最后一块的最大值还要大
        return -1;//没找到
    //2.锁定这一块的起始和终止下标,去源数据表中进行顺序查找
    start = b[i].post;
    if(i == n2-1)//说明在最后一块,最后一块没有后一块
        end = n1-1;//数组长度-1，就是最后一个有效元素下标
    else
        end = b[i+1].post - 1; //后一块的起始下标-1 得到前一块的终止下标
    //取源数据表 在start --- end之间取查找
    for(i = start; i <= end; i++)
    {
        if(x == a[i])
            return i;
    }
    return -1;//没有找到
}
int main(int argc, const char *argv[])
{
    //源数据表 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
    int a[19] = { 18, 10, 9, 8, 21, 20, 38,42, 19, 50, 51, 72, 56, 55, 76,100,
90, 88, 108};
    //索引表
    index_t b[4] = {{18, 0},{42, 4},{72, 9},{108, 14}};
    //将数组中的每个元素都查找一遍
    int i;
    for(i = 0; i < 19; i++)
    {
        printf("%d的位置下标%d\n",a[i], findByBlock(a, 19, b, 4, a[i]));
    }
    printf("%d的位置下标%d\n",66,findByBlock(a, 19, b, 4, 66));
    return 0;
}