查找算法之折半查找+分块查找

基本概念

1. 查找表：由同一种类型的数据元素（记录）组成
2. 静态查找表:只需要查找算法
3. 动态查找表：除了查找，还需要增删改查数据元素
4. 关键字:唯一标识数据元素的数据项

常见的查找算法

折半查找

概念

折半查找又称二分查找，仅适用于有序的顺序表，不能用链表。

算法

//查找算法
int binary_search(seqlist L,Elemtype key)
{
int low,high=L.TableLen-1,mid;
while(low<=high)
{
mid=(low<=high)/2;
if(L.elem[mid]==key)
return mid;
else if(L.elem[mid]>key)
high=mid-1;
else
low=mid-1;
}
return -1;
}

折半查找树的构造

1. 如果当前LOW和HIGH之间有奇数个元素，则MID分割后，左右两部分元素个数相等
2. 如果当前LOW和HIGH之间有偶数个元素，则MID分割后，左部分比右半部分少一个元素
3. 折半查找的判定树中，若MID={（LOW=HIGH）/2}向下取整，则对于任何一个节点，必有右子树结点数-左子树结点数=0或1
4. 折半查找判定树必定是平衡二叉树
5. 折半查找判定树中，只有最下面一层是不满的，因此元素个数为n时，树高h={log2（n+1）}向下取整
6. 失败结点：n+1（等于成功节点的空链域数量）

分块查找

分块查找，又称索引顺序查找，算法过程：

1. 在索引表中确定待查记录所属的分块（可顺序，可折半）
2. 在块中查找
3. 若索引表中不包含目标关键字，则折半查找索引表最终停在LOW>HIGH，要在LOW所指分块中查找