文章目录
- 顺序查找
- 二分查找
- 索引查找
- 分块查找
静态查找指的是只对表执行查找操作，并不会动态添加元素
顺序查找
在无序的序列中使用顺序查找，查找速度是最慢的。
在顺序 {1，2，3，4，5，6，7，8，9}中查找5元素的位置 ：
int 顺序查找(int* s, int n, int k)
{
int Idx = 0;
while (Idx {
Idx++;
}
if (Idx >= n)
{
return 0; //未找到返回0
}
else
{
return Idx + 1; //返回其物理位置
}
}
二分查找
在有序的序列中使用二分查找，二分查找的速度是静态查找中最快的，
int 二分查找(int* arr, int n, int k)
{
int left = 0, right = n - 1;
while (left {
int mid = left + (right - left) / 2;
if (arr[mid] {
left = mid + 1;
}
else if (arr[mid] > k)
{
right = mid - 1;
}
else
{
return mid + 1;//返回其物理位序
}
}
return 0; //没有找到返回0
}
索引查找
索引查找的查找过程：首先在索引表中查找关键字 key 对应的位置，然后根据这个位置可以获得此位置对应的序号，此序号就是对应主数据表的索引。
索引表pos：
|
地址
|
索引关键字
|
对应的序号
|
|
0
|
202101
|
1
|
|
1
|
202103
|
2
|
|
2
|
202105
|
0
|
主数据表Main：
|
地址
|
关键字
|
其他数据信息
|
|
0
|
202105
|
…
|
|
1
|
202101
|
…
|
|
2
|
202103
|
…
|
注意：索引表的索引关键字最好是有序的，我们可以在索引表中使用 二分查找。
例如，查找 202103 对应的学生：
- 通过索引表查找 202103，利用二分查找，找到之后，它所对应的序号2，就是主数据表对应此项的索引下标。
//主数据表
typedef struct
{
std::string name;
int age;
int num;
}MainTable;
//索引表
typedef struct
{
KeyType key; //用于查找的关键字
int pos; //关键字元素在主数据表中的索引
}PosTable;
int 索引查找(PosTable c[], int n, int k)
{
int left = 0, right = n - 1;
while (left {
int mid = left + (right - left) / 2;
if (c[mid].key > k)
{
right = mid - 1;
}
else if (c[mid].key {
left = mid + 1;
}
else
{
return c[mid].pos + 1; //根据索引表的地址得到对应数据表的序号，并返回逻辑序号
}
}
return 0; //没有找到
}
int main()
{
MainTable student[] = { {"张三",18,202101},{"李四",19,202103},{"赵六",25,202105},{"王五",23,202104},{"刘八",21,202107} };
PosTable pos[] = { {202101,0},{202103,1},{202104,3},{202105,2},{202107,4} };
int Idx = 索引查找(pos, 5, 202107); // 5
return 0;
}
分块查找
思路： 把主数据表的元素分成若干块，每一块的元素可以是无序或者有序的，但是块与块之间的元素一定是有序的，块有一个单独的关键字，前一个块的关键字必须大于（小于）后一个块的关键字。
typedef struct 块
{
int key; //块关键字
int low; //块内最小下标
int high; //块内最大下标
};
数据： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
- 把他们分块：[1 2 3 4] [5 6 7 8] [9 10 11 12] [13 14 15 16] [17 18 19 20]，一共有五个块。
- 每一块都具有关键字(用于查找)，low和high来存储这一块内的最小和最大下标。
|
关键字
|
low
|
high
|
|
4
|
0
|
3
|
|
8
|
4
|
7
|
|
12
|
8
|
11
|
|
16
|
12
|
15
|
|
20
|
16
|
19
|
- 把每一块的关键字当作一组数，二分查找块关键字（4，8，12，16，20），当查找到了一个数字大于前一个块，并且小于后一个块，转而到块内寻找此数据（如16： 12，13，14，15）。
//块数
#define K_NUM 4
void 分块(int* arr,int n,块*& kuai)
{
//20个元素，可以分4块，每块5个元素
int num_每块的元素 = 20 / K_NUM;
int num = 1; //每遍历n个元素，换一个块
int kIdx = 0; //每块下标
int max_value = 0;
for (int i = 0; i {
//寻找每一块的最大值
max_value = max(arr[i], max_value);
if (num == 1)
{
kuai[kIdx].low = i; //一开始，最小下标保存
num++;
}
else if (num == num_每块的元素)
{
kuai[kIdx].high = i; //结束时，最大下标保存
kuai[kIdx].key = max_value; //关键字保存块中，为块内最大的元素
num = 1; //为下一个块做准备，重新开始
kIdx++; //到下一个块
}
else
{
num++;
}
}
}
int 二分查找_块(int* arr, 块 k[], int n_kuai, int val)
{
int left = 0, right = n_kuai - 1;
int mid = 0;
while (left {
mid = left + (right - left) / 2;
if (val {
right = mid - 1;
}
else
{
left = mid + 1;
}
}
//在某块内查找
int Idx = k[right+1].low;
while (Idx {
Idx++;
}
if (Idx {
return Idx + 1; //返回逻辑位序
}
else
{
return 0; //没有找到，返回零
}
}
int main()
{
int arr[20] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 };
块* k = new 块[K_NUM]{};
//1. 数据分块
分块(arr, 20, k)
//2. 二分查找块，并且在块内寻找数据
for (int i = 20; i >= -5; i--)
{
int Idx = 二分查找_块(arr, k, 4, i);
printf("%d ", Idx); // 20 19 18 17 16 ......2 1 0 0 0 0 0
}
delete[] k;
return 0;
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
