分块查找（也称为索引顺序查找）是一种改进的顺序查找方法，它将查找表分成若干个块，并要求块内的元素有序排序，但块与块之间不要求有序。每个块内的最大元素构成一个索引表。分块查找的过程是先查找索引，确定待查元素所在的块，然后在该块内进行顺序查找。
分块查找的平均查找长度介于顺序查找和二分查找之间，适用于查找次数相对较少，而插入和删除操作频繁的线性表。
分块查找的步骤如下：
-
建立索引：首先将查找表分成若干个块，每个块内的元素不必有序，但块间必须是有序的，即第i块的每个元素都必须小于第i+1块的所有元素。
-
构建索引表：对于每个块，选择一个元素（通常是该块的最大值）放入索引表中。索引表是排序的。
-
查找过程：
- 首先在索引表中查找待查关键字所在的块，由于索引表是有序的，可以使用二分查找或顺序查找。
- 确定了所在的块后，在相应的块内进行顺序查找。
分块查找的时间复杂度主要取决于两个部分：索引查找和块内查找。如果索引表使用二分查找，那么索引查找的时间复杂度为O(log m)，其中m是块的个数。块内查找的时间复杂度为O(n/m)，其中n是元素总数。因此，平均查找长度约为O(log m + n/m)。
分块查找的优点是插入和删除操作比较方便，只需要在块内进行，而不需要移动块外的元素。这使得分块查找在某些动态变化的数据库中比较适用。
1.索引表
typedef struct
{
int
max
;
//
这块里的最大值是多少
int
post
;
//
记录这块的起始下标
}
index_t
;
2.源数据表
int
a
[
19
]
=
{
18
,
10
,
9
,
8
,
21
,
20
,
38
,
42
,
19
,
50
,
51
,
72
,
56
,
55
,
76
,
100
,
90
,
88
,
108
};
块间有序，块内无序
0
--
3 18
,
10
,
9
,
8
//
第
0
块
18
4
--
8 21 20 38 42 19
//
第
1
块
42
9
--
13 50
,
51
,
72
,
56
,
55
//
第
2
块
72
14
-
18 76
,
100
,
90
,
88
,
108
//
第
3
块
108
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;
}
结语
以上就是分块查找的使用方法，本次代码分享到此结束。
最后的最后，还请大家点点赞，点点关注，谢谢大家！
