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

@TOC

索引查找

什么是索引查找

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

算法实现

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<n;i++)
{
    if(key<a[i][0])
    {
        for(int j = a[i][1];j<a[i][1]+m;j++ )
        {
            if(b[j] == key)
            {
                cout<<j<<endl;
                break;
            }
        }
        break;
    }
    
}

实战演练

用程序实现在{8,1,4,7,18,17,13,16,2022,2019,2021,2020}里面查找13的过程。

#include <iostream>
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;i<n;i++)
    {
        if(a[i][0]>key)
        {
            for(int j=a[i][1];j<a[i][1]+m;j++)
            {
                if(b[j] == 0)
                {
                    break;
                }else{
                    if(b[j] == key)
                    {
                        length = j-a[i][1] + i + 2;
                        cout<<j<<endl;
                    }
                }
            }
            break;
        }
    }
    cout<<"平均查找长度为："<<length<<endl; 
    return 0;
 } 

效果图：

✨$\textcolor{blue}{原创不易，还希望各位大佬支持一下}$ <br/>
👍 $\textcolor{green}{点赞，你的认可是我创作的动力！}$ <br/>
⭐️ $\textcolor{green}{收藏，你的青睐是我努力的方向！}$ <br/>
✏️ $\textcolor{green}{评论，你的意见是我进步的财富！}$ <br/>