当前位置：首页 > article >正文

线性表的三种常见查找算法（顺序查找、折半查找、分块查找）及算法分析

article 2025/1/4 13:24:06

查找的基本概念

什么是查找？

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录

关键字：用来表示一个数据元素或记录的某个数据项的值
- 主关键字：可唯一的标识一个记录的关键字
- 次关键词：用以识别若干记录的关键字

查找成功与否？

若查找表中存在这样一个记录，则称“查找成功”
- 查找结果给出整个记录的信息，或指示该记录在查找表中的位置
否则称“查找不成功”
- 查找结果给出“空记录”或“空指针”

查找的目的是什么？

查询某个特定数据元素是否在查找表中
检索某个特定的数据元素的各种属性
在查找表中插入一个数据元素
删除查找表中某个数据元素

查找表的分类

静态查找表：仅作“查询”操作的查找表
动态查找表：作“插入”和“删除”操作的查找表

查找算法的评价指标

平均查找长度（ASL）：关键字的平均比较次数
$\sum^{n}_{i=1}p_ic_i$
n：记录的个数

pi：查找第i个记录的概率（通常认为是等概率的，即pi=1/n）

ci：找到第i个记录所需的比较次数

线性表的查找

顺序查找

应用范围：

顺序表或线性链表表示的静态查找表
表内元素之间无序

顺序表的表示：

typedef struct{
    KeyType key;//关键字域
    ......		//其他域
}

typedef struct{
    ElemType *R;//表基址
    int length;//表长
}SSTable;
SSTable ST;

算法

int Search_Seq(SSTable ST, KeyType key){
    //若成功返回其位置信息，否则返回0
    for(i=ST.legth;i>=1;--i) //0下标处不存储
        if(ST.R[i].key==key)
            return i;
    return 0;
}

其他形式

int Search_Seq(SSTable ST, KeyType key){
	for(i=ST.length;ST.R[i].key!=key;--i)
		if(i<=0)
            break;
    if(i>0)
        return i;
    else
        return 0;
}

为避免查找过程中每一步都要检测是否查找完毕，可将待查关键字key存入表头（称为“哨兵”）

int Search_Seq(SSTable ST, KeyType key){
    ST.R[0].key=key;
    for(i=ST.length;ST.R[i].key!=key;--i);
    return i;
}

当ST.length较大时，此改进能使进行一次查找所需的平均时间减少一半

时间效率分析

比较次数与key的位置有关：

查找第i个元素，需要比较n-i+1次
查找失败，需比较n+1次

时间复杂度：O(n)

查找成功时的平均查找长度，设表中各记录查找等概率

ASL=（1+2+…+n）/n=(n+1)/2

空间复杂度：O(1)

折半查找

设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，key为给定的要查找的值
初始时，令low=1,high=n,mid= $\lfloor(low+high)/2\rfloor$
让k与mid指向的记录比较
- 若key==R[mid].key，查找成功
- 若key<R[mid].key，则high=mid-1
- 若key>R[mid].key，则low=mid+1
重复上述操作，直到low>high，查找失败

算法

非递归实现

int Search_Bin(SSTable ST, KeyType Key){
    low=1;
    hig = ST.length;
    while(low<=high){
        mid=(low+high)/2;
        if(ST.R[mid].key==key)
            return mid;
        else if(key<ST.R[mid].key)
            high=mid-1;
        else
            low=mid+1;
    }
    return 0;
}

递归实现

int Search_Bin(SSTable ST, KeyType Key, int low, int high){
    if(low>high)
        return 0;
    mid=(low+high)/2;
    if(key===ST.R[mid].key)
        return mid;
    else if(key<ST.R[mid].key)
        Search_Bin(ST, key, low, mid-1);
    else
        Search_Bin(ST, key, mid+1, high);
}

算法分析

首先引入判段树的概念

将查找过程中比较次数相同的结点放在树的同一层，构成判断树
在这里插入图片描述

圆形为内部结点，代表查找成功的情况

矩形为外部结点，代表查找不成功的情况

查找成功：比较次数=路径上的结点数=结点的层数

比较次数≤树的深度= $\lfloor log_2n\rfloor+1$

查找不成功：比较次数=路径上的内部结点数

ASL:

设表长n=2^h-1，则 $h=log_2(n+1)$ ，此时判段树为深度=h的满二叉树，且表中每个记录的查找概率相等：pi=1/n
$ASL_{succ} = \sum^n_{i=1}p_ic_i = \frac{1}{n}\sum^h_{j=1}j \times 2^{j-1}=\frac{n+1}{n}log_2(n+1)-1 \approx log_2(n+1)-1 \quad (n>50)$
其中，j为第j层每个结点要比较的次数， $2^{j-1}$ 为第j层结点数

时间复杂度：O(logn)

优点：查找效率高

缺点：只适用于有序表，且限于顺序存储结构，对链表无效

分块查找

条件：

将表分为几块，且表分块有序。若i<j，则第j块中所有记录的关键字均大于第i块中的最大关键字。
建立“索引表”，每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序

查找过程：先确定待查找记录所在块（顺序查找或折半查找），再在块内查找（顺序查找）

算法分析

查找效率：ASL=索引表查找的ASL+块内查找的ASL
$ASL_{succ} \approx log_2(\frac{n}{s}+1)+\frac{s}{2}\quad (log_2n \le ASL_{succ}\le\frac{n+1}{2})$
其中，s为每块内部的记录个数，n/s即块的数目