【21天算法学习】索引查找

作者简介：
🍀姓姜，字君竹。
🍁浅薄观点：科以载文，文以载道
🌱软件技术升计科，计划考研
🌾要有最朴素的生活和最遥远的梦想，即使明日，天寒地冻，路遥马亡​​​

1. 概念及介绍
     索引查找主要氛围基本索引查找和分块查找，核心思想是对于无序的数据集合，先建立所以表，是的索引表有序和或分块有序，结合顺序查找与索引查找的方法完成查找。
     基本索引查找是基于一个有序的索引表进行折半查找，然后再根据索引表与主数据表的关系确定数据所在位置的过程。所以只需要在折半查找后，从索引中取出该元素在主数据集合中对应的位置即可。
     使用分块查找时，主数据表必须满足该规律：按一定的区间长度进行分块后，前一块中的最大关键字小于后一块中的最小值，即后一块中的任意元素都大于前一块中的所有元素，关键字存储的就是这一块中足底啊的关键字的值。
   在进行分块查找时易燃是先在索引表上进行折半查找，确定待查元素所在分块。由于分块内部的元素无序，所以分块内部（基于快索引表的快区间端点）再食用顺序查找确定元素的最终位置。
2. 时间空间复杂度
   2.1 基本索引查找：
     对于完整的索引查找，整个过程包含索引的建立和元素的查找两个步骤。对于索引表的建立可以使用不同的排序算法时效内，有可能有多种情况。索引表是一个有序的集合，先在此基础上进行折半查找，然后根据索引表中存储的信息提取出对应的位置，此处为常数级O(1)。所以对于查找部分，时间复杂度与折半查找为通过一下级别：O(log₂n)。
     对于基本索引表，相当于是对主数据进行排序后完整的存储下来，因此除去一些临时变量外，主要需要对索引表分配额外的存储空间，与输入数据的量级相同：O(n)。
   2.2 分块查找：
     对于分块查找，需要主数据表本身满足一定的规律，在此之上只需要指定一个合理的区间长度，就可以得到一个分块索引表，主要的消耗在于存储，所以分块查找可以看做是两次查找：分块的折半查找和分块内的顺序查找。时间复杂度不会超过O(n)。
     由于选定的区间长度不唯一，所以需要的存储空间也不确定，一班为n/a，a为常数，最多也不会超过O(n)。
3. 图解
   3.1 基本索引查找：

3.2 分块查找：
4. 代码实现
4.1 基本索引查找：
4.2分块查找：

又停电了，之后再补，烦死了。

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

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。