1. 计算机考研：数据结构常用算法解析(8)
第九章 查找
查找分成静态查找和动态查找，静态查找只是找，返回查找位置。而动态查找则不同，若查找成功，返回位置，若查找不成功，则要返回新记录的插入位置。也就是说，静态查找不改变查找表，而动态查找则会有插入操作，会改变查找表的。
不同的查找所采用的存储结构也不同，静态查找采用顺序表，而动码迟态查找由于经常变动，所以用二叉排序树，二叉平衡树、B-和B+。
静态查找有，顺序查找，折半查找，分块查找(索引顺序查找)
顺序查找(Sequential Search)是最简单的一种查找方法。
算法思路
设给定值为k，在表(R1 R2……Rn)中，从Rn即最后一个元素开始，查找key=k的记录。若存在一个记录Ri(l≤i≤n)的key为k，则查找成功，返回记录序号i;否则，查找失败，返回0。
算法描述
int sqsearch(sqlist r,keytype k) //对表r顺序查找的算法//
{ int i;
r.data[0].key=k; //k存入监视哨//
i=r.len; //取表长//
while(r.data[i].key!=k)
i--; //顺序查找//
return(i);
}
算法用了一点技巧：先将k存入监视哨，若对某个i(≠0)有r.data[i].key=k，则查找成功，返回i;若i从n递减到1都无记录的key为k，i再减1为0时，必有r.data[0].key=k，说明查找失败，返回i=0。
平均查找成功长度ASL= ，而查找失败时，查找次数等于n+l。
折半查找算法及分析
当记录的key按关系≤或≥有序时，不管是递增的还是递减的，只要有序且采用顺序存储。
算法描述
int Binsearch(sqlist r,keytype k) //对有序表r折半查找的算法//
{ int low,high,mid;
low=1;high=r.len; //上下界初值//
while(low<=high) //表空间存在时//
{ mid=(low+high)/2; //求当前mid//
if (k==r.data[mid].key)
return(mid); //查找成功，返回mid//
if (k
high=mid-1; //调整上界，向左部查找//
else
low=mid+1; //调整下界，向右部查找//
}
return(0); //low>high，查找失败//
}
判定树：用来描述二分查找过程的二叉树。n个结点的判定树的深度和n个结点的完全二叉树深度相同= 。但判断树不一定是完全二叉树，但他的叶子结点所在层次之差不超过1。所以，折半查找在查找成功时和给定值进行比笑困较的关键字个数至多为
ASL=
分块查找算法及分析
分块查找(Blocking Search)，又称索引顺序查找(Indexed Sequential Search)，是顺序查找方法的一种改进，目的也是为了提高查找效率。
1.分块
设记录表长为n，将表的n个记录分成b= 个块，每块s个记录(最后一块记录数可以少于s个)，即：
且表分块有序，即第i(1≤i≤b-1)块所有记录的key小于第i+1块中记录的key，但块内记录可以无序。
2.建立索引
每块对应一索引项：
KeymaxLink
其中Keymax为该块内记录的最大key;link为该块第一记录的序号(或指针)。
3.算法思路 分块索碰模念引查找分两步进行：
(1)由索引表确定待查找记录所在的块;(可以折半查找也可顺序因为索引表有序)
(2)在块内顺序查找。(只能用顺序查找，块内是无序的)
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/
2. 数据结构 顺序查找的平均比较次数不是1+n/2吗为什么是n/2
你是对的，这个答案错了，
顺序表查找来说，最好的就是一次就可以找到，时间复杂度是O（1）
最坏是要比较n次,O(n)
如果查找不成功，要进行n+1次比较
由于关键字在任何一个位置的概率都是相同的，所以平均查找次数是n+1/2，时间复杂度还是O（n）
3. 顺序表长度为n的折半查找算法的平均查找长度
折半查找算法在顺序表长度为n的情况下，其平均查找长度可以用对数函数来表示。具体而言，该算法的平均查找长度为log(n)，这里的对数是以2为底。
折半查找，也称为二分查找，是一种高效的查找算法。它通过将查找区间逐步缩小一半的方式，快速定位到目标元素。在长度为n的有序列表中，查找过程可以看作是对列表进行对数级的划分。
假设列表中有n个元素，初始查找区间为整个列表。每次比较后，可以将查找区间缩小一半。因此，查找过程最多需要进行log(n)次比较，这里的log是以2为底。
平均查找长度是指在最坏情况和最好情况之间的查找长度的平均值。对于折半查找，由于每次查找都会使查找区间缩小一半，所以平均查找长度同样可以用log(n)来表示。
需要注意的是，折半查找要求输入数据必须是有序的。如果数据是无序的，则需要先进行排序，这将增加额外的时间成本。
折半查找算法的时间复杂度为O(log(n))，这使得它在处理大规模数据时表现出色。然而，当数据量较小或者数据分布不均匀时，其优势可能不明显。
总结来说，顺序表长度为n的折半查找算法的平均查找长度为log(n)，这里的对数是以2为底。这种算法在有序列表中具有较高的查找效率，是许多实际应用中的重要工具。
4. 检索和索的区别是什么
1、顺序查找的基本思想
基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。
2、顺序查找的存储结构要求
顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作存储结构时，扫描必须从第一个结点开始）。
3、基于顺序结构的顺序查找算法
（1）类型说明
typedef struct{
KeyType key；
InfoType otherinfo； //此类型依赖于应用
}NodeType；
typedef NodeType SeqList[n+1]； //0号单元用作哨兵
（2）具体算法
int SeqSearch(Seqlist R，KeyType K)
{ //在顺序表R[1..n]中顺序查找关键字为K的结点，
//成功时返回找到的结点位置，失败时返回0
int i；
R[0].key=K； //设置哨兵
for(i=n；R[i].key!=K;i--)； //从表后往前找
return i； //若i为0，表示查找失败，否则R[i]是要找的结点
} //SeqSearch
④顺序查找的优点
算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。
⑤顺序查找的缺点
查找效率低，因此，当n较大时不宜采用顺序查找
索引查找分两步进行：
① 将外存上含有索引区的页块送人内存，查找所需记录的物理地址
② 将含有该记录的页块送人内存
注意：
①索引表不大时，索引表可一次读入内存，在索引文件中检索只需两次访问外存：一次读索引，一次读记录。
②由于索引表有序，对索引表的查找可用顺序查找或二分查找等方法。
5. 写出顺序表上将监视哨设在高端的顺序查找算法子程序
监视哨一般放在a[0]上，将要查找的数据f先赋值给a[0]，然后从后往前找，不设边界条件，因为即使a[1]-a[n]之间没有f，也可以在最后a[0]找到f，代表没查找到。
int find(int a[] , int f) //可以把类型改下
{
a[0]=f;
for(i=n;a[i]!=f;i++); //不用判断是不是越界。
return i; //如果i是0，代表没找到，不是0，则返回数组位置。
}
6. 顺序表的顺序查找和二分查找
顺序查找,二分查找和哈希查找算法,它们各自的特点是：
1.对比顺序查找的特点就是从表的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功;如果到最后一个元素仍没有目标元素，则查找失败。
2.二分查找的特点就是从表中间开始查找目标元素。如果找到一致元素，则查找成功。如果中间元素比目标元素小，则仍用二分查找方法查找表的后半部分(表是递增排列的)，反之中间元素比目标元素大，则查找表的前半部分。
3.哈希算法的特点是是使用给定数据构造哈希表，然后在哈希表上进行查找的一种算法。先给定一个值，然后根据哈希函数求得哈希地址，再根据哈希地址查找到要找的元素。是通过数据元素的存储地址进行查找的一种算法。
7. 编写无序顺序表顺序查找、有序顺序表顺序查找、二分查找算法。用c语言。高分急求！
int IdxSerch(SeqList A[],IdxType index[],int b,KeyType k,int n) {
//分块查找关键字为k的记录，索引表为
index[0..b-1]
int low=0,high=b-1,mid,i;
int s=n/b; //每块记录个数
while(low<=high)
{
//在索引表中进行二分查找，找到的位置放在low中
mid=(low+high)/2;
if(index[mid].key<k) low=mid+1；
else high=mid-1;
}
if(low<b)
{
//在顺序表中顺序查找
for(i=index[low].link;i<=index[low].link+s-1 && i<n;i++)
if(A[i].key==k) return i;
return -1;
}
return -1;
}
typedef struct node
{
KeyType key;
//结点中的关键字
struct node *lchild,*rchild; //左、右孩子指针
}BsTree;
BsTree *BstSeareh(BsTree *BST,KeyType k ,BsTree **parent)
{
BsTree *p=BST,*q=NULL; //p指向根结点，q指向*p的双亲
while(p!=NULL)
{
if(k==p->key)
{ //查找成功
*parent=q;
return (p);
}
q=p;
if(k<p->key) p=p->lchild；
//在左子树中查找
else p=p->rchild; //在右子树中查找
}
*parent=q;
return (p);
//查找失败，返回空
}