经典算法之索引查找

活动地址：CSDN21天学习挑战赛

前言：
✌ 作者简介：游坦之 ✌
🏆 大学软件工程在读，希望学到真本领，经世致用 🏆
📫 如果文章知识点有错误的地方，请指正！和大家一起学习，一起进步👀
💬 人生格言：成好人，行好事，做儒猿💬
🔥 如果感觉博主的文章还不错的话，还请👍关注、点赞、收藏三连支持👍一下博主哦

索引查找

什么是索引查找

​ 索引查找是在索引表和主表进行的查找，存储结构是线性表。索引查找是将表分成几块，并且块内无序，块间有序；先确定待查记录所在的块，再在块内查找。

算法实现

1、用数组存放待查记录，每个数据元素至少含有关键字域

2、建立索引表，每个索引表结点含有最大关键字域和指向本快第一个结点的指针，例如下图。

、

举个栗子

​ 对下图查找13，首先现在索引表（最大关键字表）里面查找，因为这个是有序的，第n+1总是比第n块里的所有元素要大。

​ 13是小于18而大于8的，所以如果13在这个表里面，他只可能存在于18该分块中。

​ 于是在18分块，也就是坐标4-8中进行顺序查找，查找了三次找到了13，也就是说总共查找了2+3次。

​ 因此，平均查找长度为ASLbc = Lb + Lc；

​ Lb：查找索引表确定所在块的平均查找长度。

​ Lc：在块中查找元素的平均查找长度。

伪代码

//用数组表示
int a[M][M] = {{8,0},{18,4},{2022,8}};
int b[M] = {8,1,4,7,18,17,13,16,2022,2019,2021,2020};
int key;
int n;//索引表的元素个数
int m;//块中的元素个数
for(int i=0;i

#include 
using namespace std;
int n = 3;
int m = 4;
int a[3][2] = {{8,0},{18,4},{2022,8}};
int b[12] = {8,1,4,7,18,17,13,16,2022,2019,2021,2020};
int key = 13;
int length = 0;
int main()
{
	
	for(int i=0;ikey)
		{
			for(int j=a[i][1];j