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. 数据结构中有哪些查找算法
和二分查找性能接近的：既然可以二分查找，那么关键字肯定可以满足全序关系。那么可以用二叉查找树，一般的就是平摊O(logn),最坏O(n)。如果用平衡树，如AVL,Treap,Splay等等，可以做到保持O(logn)的界。
比二分查找性能更优的：大概只有Hash了吧。如果Hash函数设计的好，基本可以认为是O(1)的。这个你最好系统学习一下，尤其是字符串的Hash函数。
3. 数据结构中关于数据查询的算法有哪些
数据查询分静态查找和动态查找：
静态查找有：顺序查找、有顺序表的折半查找、分块查
动态查找主要用二叉排序数查找。
哈希表 常用的哈希函数有；直接寻址法，除留余数法，数字分析法，平方取中法，折叠法。
一般情况下这些就够用了
4. 数据结构 顺序查找算法和折半查找算法
//顺序查找
int findKey(int array[], int length, int key)
{
for (int i = 0; i < length; i++)
if (array[i] == key)
return i;
return -1;
}
//折半查找
int findKeybyBinary(int array[], int low, int high, int key)
{
if (low > high)
return -1;
int mid = (low + high)/2;
if (array[mid] == key)
return mid;
else if (array[mid] < key)
return findbyBinary(array,mid + 1,high, key);
else
return findbyBinary(array,low,mid - 1, key);
}
查找key=41的算法： 比较次数：3次
void main ()
{
int array[] = {8，15，19，26，33，41，47，52，64，90};
printf("the pos of 41 is %d \n", findKeybyBinary(array, 0, 9, 41));
}
查找key=35的算法： 比较次数：6次
void main ()
{
int array[] = {12，76，29，15，62，35，33，89，48，20};
printf("the pos of 41 is %d \n", findKey(array, 10, 35));
}
5. 数据结构与算法顺序查找和折半查找
1.顺序查找
又称线性查找，主要用于在线性表中进行查找。
一般线性表的顺序查找：
从线性表的一端开始，逐个检查关键字满足给定条件。若查找到某个元素的关键字满足给定条件则查找成功，返回该元素在线性表中的位置。若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。
有序表的顺序查找：
假设表L是按关键字从小到大排列的，查找的顺序是从前往后，待查找元素的关键字为key。当查找到第i个元素时，发现第i个元素对应的关键字小于key，但第i+1个元素对应的关键字大于key，这时就可以返回查找失败的信息。
2.折半查找
又称二分查找，它仅适用于有序的顺序表
首先将给定值key与表中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置。若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止。或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
3.分块查找
又称按索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找
将查找表分为若干子块。块内的元素可以无序，但块之间是有序的，第一个块中的最大关键字小于第二个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列