查找

查找的基本概念

1. 查找：在数据集合中寻找满足某种条件的数据元素的过程
2. 查找表：用于查找的数据集合。一般进行操作有
   1. 查询某个特定元素是否在查找表中
   2. 检索满足条件的某个特定的数据元素的各种属性
   3. 在查找表中插入一个数据元素
   4. 从查找表中删除某个数据元素
3. 静态查找表：查找表的操作只涉及上述1、2操作。对应的涉及3、4操作的为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；适合动态查找表的查找方法有BST的查找、散列查找等
4. 关键字：数据元素中唯一标识该元素的某个数据项的值。基于关键字的查找必须唯一
5. 平均查找长度ASL：平均一次查找中需要比较的关键字次数。是衡量查找算法效率的主要因素

顺序查找和折半查找

顺序查找

又称线性查找，适用于顺序表和链表

一般线性表的顺序查找

基本思想：从线性表的一端开始，逐个检查关键字

王道考研书给出的代码实现，这个哨兵个人感觉有点脱裤子放屁

// 表的数据结构
typedef struct{
    ElemType *elem; // 元素存储空间基址，建表时按实际长度分配，0号单元留空
    int TableLen;   // 表的长度
}SSTable;
// 顺序查找
int Search_Seq(SSTable ST, ElemType key){
    ST.elem[0] = key;   // 哨兵
    for(int i=ST.TableLen; ST.elem[i]!=key; --i){}
    return i;
}

有序表的顺序查找

为了减少查找失败时的ASL

基本思想：查找到有元素小于key和有元素大于key，则根据有序，可以直接判定查找失败

折半查找

又称二分查找，仅适用于有序的顺序表

int Binary_Search(SeqList L, ElemType key){
    int left = 0, right = L.TableLen-1;
    while(left < right){
        int mid = left+((right-left)>>1);
        if(L.elem[mid] < key){
            left = mid+1;
        }else{
            right = mid;
        }
    }
    return L.elem[left] == key ? left : -1;
}

时间复杂度：O(log(2, n))

折半查找不适用于链式存储结构

折半查找对应的判定树是一棵平衡二叉树

分块查找

又称索引顺序查找，结合了顺序查找和折半查找的优点

基本思想：将查找表分为若干子块，子块内可以无序，但子块间必须有序

赏

谢谢你请我吃糖果

支付宝

微信