江小南

V1

2023/03/21阅读:33主题:萌绿

【数据结构】折半查找、分块查找

1. 折半查找

1. 算法思想

折半查找又称“二分查找”,它仅适用于有序顺序表

顺序表有随机访问的特性,链表没有

折半查找的基本思想:首先将给定值key与表中中间位置的元素比较,若相等,则查找成功,返回该元素的存储位置;若不等,则要查找的元素只能在中间元素以外的前半部分或后半部分。比如在查找表升序排列时,若给定值key大于中间元素,则所查找的元素只能在后半部分。然后再缩小的范围内继续进行同样的查找,如此重复,直到找到为止。或确定表中没有所需要查找的元素,则查找不成功,返回查找失败的信息。

2. 代码实现

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
}

3. 查找效率分析

4. 折半查找判定树的构造

如果当前low和high之间有奇数个元素,则mid分隔后,左右两部分元素个数相等

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

判定树节点关键字:左<中<右,满足二叉排序树的定义。

失败结点:n+1(等于成功结点的空链域数量)。

2. 分块查找

1. 算法思想

特点:块内无序,块间有序

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

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

2. 代码实现

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

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

3. 用折半查找查找索引

查找目标包含在索引表的情况

查找目标不包含在索引表的情况

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

如果low超出了索引范围,则查找失败。

4. 查找效率分析

3. 小结

若查找表是“动态查找表”,使用链式存储效率更高。

分类:

后端

标签:

数据结构与算法

作者介绍

江小南
V1