【ALG 算法】022 | 顺序查找、二分查找

柠檬沙棘1996

互联网行业工程师

[69] 查找基本概念

例如：在信息表中，姓名无法作为关键字，但是身份证号可以（唯一性）

1.对查找表的常见操作

查找符合条件的数据元素；

静态查找表，仅关注查找速度即可。

插⼊、删除某个数据元素；

动态查找表，除了查找速度，也要关注插/删操作是否⽅便实现。

2.查找算法的评价指标

ASL = \sum_{i=1}^n P_i C_i

其中，n代表数据元素个数， P_i 代表第i个元素的概率， C_i 代表第i个元素的查找长度。通常认为查找任何⼀个元素的概率都相同。在二叉搜索树（BST）中曾经提及 ASL 的计算，以左边的二叉树为例：

总平均查找长度： ASL = (1 × 1 + 2 × 2 + 3 × 4 + 4 × 1)/8 = 2.62

因此，总平均查找长度： ASL = (3 × 7 + 4 × 2)/9 = 3.22

右侧二叉树的平均查找长度也同理可以计算。
ASL 的数量级反应了查找算法时间复杂度。评价⼀个查找算法的效率时，通常考虑查找成功、查找失败两种情况的 ASL 。

[70] 顺序查找

1.顺序查找的算法思想

顺序查找，⼜叫“线性查找”，通常⽤于线性表。
算法思想：从头到脚挨个找（或者反过来也OK）。

查找实现

例如以线性表为例，

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

// 顺序查找，寻找值为key的数组下标
int Search_Seq(SSTable ST, ElemType key)
{
    int i;

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

哨兵模式

也可以用“哨兵”方法来实现顺序查找：

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

// 顺序查找
int Search_ Seq(SSTable ST, ElemType key)
{
    // 哨兵
    ST.elem[0] = key;
    // 查找成功，则返回元素下标; 查找失败，则返回0
    for(i = ST.TableLen; ST.elem[i] != key; --i){
        return i;
    }
}

使用0号位置存储“哨兵”，即要查找的元素，后尾向头部依次遍历搜索。

如果成功，则返回序数，失败则返回0。
优点：⽆需判断是否越界（最终一定会结束循环），效率更⾼（但是也高不了多少，因为阶数一样）。

[71] 折半查找

1.查找过程推演

折半查找，⼜称“⼆分查找”，仅适⽤于有序、具有随机存取的顺序表。链表不具备随机存取的特点，不适用于二分查找。
【问题】
在数组 {7,10,13,16,19,29,32,33,37,41,43} 顺序表中查找33，并返回其位序。

查找失败的例子暂时省略，依照查找成功可以推演。
算法程序实现：

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

// 以升序排序的顺序表为例
int BinarySearch(SSTable L, ElemType target)
{
    int low = 0, high = L.Table - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;         // 对序数取半
        if (L.elem[mid] == target){
            return mid;                 // 查找成功直接返回序数
        }
        else if (L.elem[mid] > target){
            high = mid - 1;             // 开始从前半部分查找
        }
        else {
            low = mid + 1;              // 开始从后半部分查找
        }
    }
    return -1;                          // 查找失败，返回-1值
}