目录
一、查找的基本概念
二、顺序查找 （线性查找）
1、基本思想
2、核心代码
3、顺序查找设置哨兵
4、顺序查找的优点：
5、顺序查找的缺点：
6、折半查找
7、折半查找判定树
8、线性表查找的特点
三、索引顺序表（分块查找）
1、分块查找表存储结构
2、分块查找的基本思想
3、分块查找的代码举例
静态查找表主要有三种结构：
（1）顺序表；
（2）有序顺序表；
（3）索引顺序表。
针对静态查找表的查找算法主要有：
（1）顺序查找（线性查找）；
（2）折半查找（二分查找）；
（3）分块查找（索引顺序查找）。
一、查找的基本概念
列表：由同一类型的数据元素组成的集合。
关键码：数据元素中的某个数据项，可以标识列表中的一个或一组数据元素。
键值：关键码的值。
主关键码：可以唯一地标识一个记录的关键码。
次关键码：不能唯一地标识一个记录的关键码。
查找：在具有相同类型的记录构成的集合中找出满足给定条件的记录。
查找的结果：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败。
静态查找：不涉及插入和删除操作的查找 。
动态查找：涉及插入和删除操作的查找。
静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作; 或经过一段时间的查找之后，集中地进行插入和删除等修改操作；
动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。
查找结构：面向查找操作的数据结构 ，即查找基于的数据结构。
线性表：适用于静态查找，主要采用顺序查找技术、折半查找技术。
树表：适用于动态查找，主要采用二叉排序树的查找技术。
散列表：静态查找和动态查找均适用，主要采用散列技术。
二、顺序查找 （线性查找）
1、基本思想
从线性表的一端向另一端逐个将关键码与给定值进行比较，
若相等，则查找成功，给出该记录在表中的位置；
若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。
2、核心代码
int LineSearch::SeqSearch(int k){ i=n;while (i>0 && data[i]!=k)i--;return i; }3、顺序查找设置哨兵
哨兵就是待查值，将哨兵放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。
4、顺序查找的优点：
算法简单而且使用面广。
对表中记录的存储结构没有任何要求，顺序存储和链接存储均可；
对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。
5、顺序查找的缺点：
平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低
6、折半查找
（1）适用条件：
线性表中的记录必须按关键码有序；必须采用顺序存储。
（2）基本思想：
在有序表中（low, high,low<=high），取中间记录作为比较对象。
若给定值与中间记录的关键码相等，则查找成功；
若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；
若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。
不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。
7、折半查找判定树
判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。
通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。
（1）当n=0时，折半查找判定树为空；
（2）当n＞0时，折半查找判定树的根结点为mid=(n+1)/2，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。
（3）判定树的特点
任意两棵折半查找判定树，若它们的结点个数相同，则它们的结构完全相同。
具有n个结点的折半查找树的高度为：
（4）判定树的性质
任意结点的左右子树中结点个数最多相差1
任意结点的左右子树的高度最多相差1
任意两个叶子所处的层次最多相差1
（5）折半查找性能分析
具有n个结点的折半查找判定树的深度为：
查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。
查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数（失败情况下的平均查找长度等于树的高度）
8、线性表查找的特点
线性表查找是静态的查找，要在线性表上进行动态查找，存在以下的问题：
（1）无序顺序表上进行动态查找，插入操作简单，但查找的复杂性高。
（2）有序顺序表上进行动态查找，查找的时间复杂性好，但是插入操作时间复杂性高。
（3）单链表上进行动态查找，插入操作简单，但查找操作复杂性高。
（4）解决办法：采用二叉树这种数据结构，实现动态查找。
三、索引顺序表（分块查找）
1、分块查找表存储结构
查找表由"分块有序"的线性表和索引表组成。
（1）"分块有序"的线性表
表R[1…n]均分为b块，前b-1块中结点个数为s=[n/b]，第b块的结点数小于等于s；每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是"分块有序"的。（2）索引表
抽取各块中的最大关键字及其起始位置构成一个索引表ID[l…b]，即IDi中存放第i块的最大关键字及该块在表R中的起始位置。由于表R是分块有序的，所以索引表是一个递增有序表。
2、分块查找的基本思想
（1）首先查找索引表
索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。
（2）然后在已确定的块中进行顺序查找
由于块内无序，只能用顺序查找。
3、分块查找的代码举例
/**《DS静态查找之顺序索引查找》 题目描述： 给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始 要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。输入： 第一行输入n，表示主表有n个数据 第二行输入n个数据，都是正整数，用空格隔开 第三行输入k，表示主表划分为k个块，k也是索引表的长度 第四行输入k个数据，表示索引表中每个块的最大值 第五行输入t，表示有t个要查找的数值 第六行起，输入t个数值，输入t行输出： 每行输出一个要查找的数值在队列的位置和查找次数，数据之间用短划线隔开，如果查找不成功，输出字符串error */#include <iostream> #include<vector> using namespace std; int block[50][50][2]; //第一维存放块，第二维度存放数，第三维度存放 数的序号 void func(int n, int k) {int find, cnt = 0; //cnt判断查找次数 cin >> find;for (int i = 0; i < k; i++) {cnt++;if (find > block[i][0][0]) { //判断需找的数在哪个块 continue;}for (int j = 1; ; j++) {cnt++;if (find == block[i][j][0]) {cout << block[i][j][1] + 1 << "-" << cnt << "\n";return;}if (block[i][j][0] == 0) { //即当前的维度已经空了break;}}}cout << "error\n";return; }int main() {int n, * arr;int k;cin >> n;arr = new int[n + 3];for (int i = 0; i < n; i++) {cin >> arr[i];}cin >> k;for (int i = 0; i < k; i++) {cin >> block[i][0][0]; //存放块 }for (int i = 0; i < n; i++) {for (int j = 0; j < k; j++) {if (arr[i] <= block[j][0][0]) {//小于当前块则可以存放进去 int x = 1;while (1) {if (block[j][x][0] == 0) { //找到第一个空位存放数 block[j][x][0] = arr[i];block[j][x][1] = i; // 存放序号 break;}x++;}break;}}}//----------------查找int t;cin >> t;while (t--) {func(n, k);}delete[]arr;return 0; }/** 输入： 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 3 22 48 86 6 13 5 48 40 53 90 输出： 3-4 error 12-8 error 18-9 error */
我是花花，祝自己也祝您变强了~
