数据结构 408-7-1&2 - 数据结构 - 计算机科学 | Flüstern = Whispering's Blog = 无需过去，无关未来，只有现在

# 查找的基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找

查找表 (查找结构)：用于查找的数据集合称为查找表，它由同一类型的数据元素 (或记录) 组成

关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的

# 对查找表的常见操作

查找符合条件的数据元素
插入、删除某个数据元素

静态查找表：只需进行查操作（仅关注查找速度）；动态查找表：需支持增删查功能（除了查找速度，也要关注插 / 删操作是否方便实现）

# 查找算法的评价指标

查找长度：在查找算法中，需要对比关键字的次数称为查找长度

平均查找长度 (ASL)：所有查找过程中进行关键字的比较次数的平均值

评价一个查找算法的效率时，通常考虑查找成功 / 查找失败两种情况的 ASL

# 顺序查找

顺序查找，又叫 "线性查找"，通常用于线性表

算法思想：从头到尾全部遍历

typedef struct{       //查找表的数据结构(顺序表)
    ElemType* elem;   //动态数组基址
    int TableLen;     //表的长度
}SSTable;

//顺序查找
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0;i<ST.TableLen && ST.elem[i]!=key;++i);
    //查找成功，则返回元素下标；查找失败，则返回-1
    return i==ST.TableLen?-1:i;
}

//顺序查找(哨兵)
//优点：无需判断是否越界，效率更高
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;    //哨兵，0号位置存哨兵
    int i;
    for(i=ST.TableLen;ST.elem[i]!=key;--i); //从后往前找
    return i;   //查找成功，则返回元素下标；查找失败，则返回0
}

查找效率分析：

$ASL_{success}=\dfrac{n+1}{2}$ ； $ASL_{fail}=n+1$

顺序查找的优化 (对有序表)：查找表中元素有序存放 (递增 / 递减)

ASL_{fail}=\dfrac{n}{2}+\dfrac{n}

用查找判定树分析 ASL：

一个成功节点的查找长度 = 自身所在层数
一个失败结点的查找长度 = 其父节点所在层数
默认情况下，各种失败情况或成功情况都等概率发生

顺序查找的优化 (被查概率不相等)：被查概率大的放在靠前的位置

优点：查找成功时 ASL 更少

# 折半查找

折半查找，又称 "二分查找"，仅适用于有序的顺序表（区别于链表）

typedef struct{       //查找表的数据结构(顺序表)
    ElemType *elem;   //动态数组基址
    int TableLen;     //表的长度
}SSTable;

//折半查找
int Binary_Search(SSTable L,ElemType key){
    int low=0,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 分隔后，左右两部分元素个数相等

如果当前 low 和 high 之间有偶数个元素，则 mid 分隔后，左半部分比右半部分少一个元素

折半查找的判定树中，若 $mid=\lfloor (low+high)/2\rfloor$ ，则对于任何一个结点，必有：右子树节点数 - 左子树节点数 = 0 或 1

折半查找的判定树一定是平衡二叉树，折半查找的判定树中，只有最下面一层时不满的，因此，元素个数为 n 时树高为 $h=\lceil log_2(n+1)\rceil$

判定树结点关键字：左 <中 < 右，满足二叉排列树的定义，失败节点：n+1 个 (等于成功节点的空链域数量)

查找成功 ASL<=h，查找失败的 ASL<=h，折半查找的时间复杂度 = $O(log_2n)$

# 分块查找

将数组分为多块，建立索引表，"索引表" 中保存每个分块的最大关键字和分块的存储区间

特点：块内无序，块间有序

//索引表
typedef struct {
    ElemType maxValue;
    int low,high;
}Index;

//顺序表存储实际元素
ElemType List[100];

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

在索引表中确定待查记录所属的分块 (可顺序、可折半)
在块内顺序查找

用折半查找查索引表：若索引表中不包含目标关键字，则折半查找索引表最终停在 low>high，要在 low 所在分块中查找

原因：最终 low 左边一定小于目标关键字，high 右边一定大于目标关键字。而分块存储的索引表保存的是各个分块的最大关键字

# 查找效率分析 (ASL)

ASL = 查索引表的平均查找长度 + 查分块的平均查找长度

假设，长度为 n 的查找表被均匀分为 b 块，每块 s 个元素

设索引查找和块内查找的平均查找长度分别为 $L_I,L_S$ ，则分块查找平均查找长度为 $ASL=L_I+L_S$

用顺序查找索引表，则 $L_I=\dfrac{b+1}{2},L_S=\dfrac{s+1}{2}$ ，则 $ASL=\dfrac{s^2+2s+n}{2s}$ ，当 $s=\sqrt{n}$ 时， $ASL_{min}=\sqrt{n}+1$

用折半查找索引表，则 $L_I=\lceil log_2(b+1)\rceil,L_S=\dfrac{s+1}{2}$ ，则ASL=\lceil log_2(b+1)\rceil+\dfrac{s+1}

数据结构考研408