22 顺序查找、二分查找.md

#数据结构 #算法 #C

[77] 查找基本概念

• 查找 ：在数据集合中寻找满⾜某种条件的数据元素的过程称为查找。
• 查找表（查找结构）：⽤于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成
• 关键字 key：数据元素中唯⼀标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的。
  例如：在信息表中，姓名无法作为关键字，但是身份证号可以（唯一性）

1.对查找表的常见操作

1. 查找符合条件的数据元素；
   • 静态查找表，仅关注查找速度即可。
2. 插⼊、删除某个数据元素；
   • 动态查找表，除了查找速度，也要关注插/删操作是否⽅便实现。

2.查找算法的评价指标

1. 查找长度： 在查找运算中，需要对比关键字的次数称为查找⻓度。
2. 平均查找长度（ASL, Average Search Length）：
   所有查找过程中进⾏关键字的⽐较次数的平均值：

$$ASL=\sum _{i=1}^n{P}_i{C}_i$$

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

• 查找成功，共有8种可能性（8个结点）
  第一层的查找次数为1，第二层的查找次数为2（必须先与50对比，发现不是50，才可能到第二层），同理，第三层查找次数为3，第4层查找次数为4。

总平均查找长度： $ASL=(1\times 1+2\times 2+3\times 4+4\times 1)/8=2.625$

• 查找失败，共有9种可能性，因为有8个结点划分了9个区间段，落在任意一个区间段的概率时相等的。
  除了60 ~ 68，68 ~ 70 这两个区间段（不包含边界值）需要四次查找外，其均需要三次查找。

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

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

[78] 顺序查找

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。
优点：⽆需判断是否越界（最终一定会结束循环），效率更⾼（但是也高不了多少，因为阶数一样）。

查找效率分析

查找成功，每一个元素查找的可能性均等：
${ASL}_s=\frac{1+2+3+...+n}{n}=\frac{n+1}{2}$

因为查找元素为 $n$ 个，每个查找元素的概率均等，都是 $\frac{1}{n}$ ，其总期望见上。
${ASL}_f=n+1$
总体时间复杂度: $O(N)$ 。

2. 顺序查找的优化（对有序表）

如果原顺序表，本来就是有顺序的（递增或者递减排序），在查找到某个元素（大于或者小于）要寻找的值的时候，对后续的元素就不需要再进行判定了。
原有对顺序表的判定将转化成为“判定树”结构。

⼀个成功结点的查找⻓度 = ⾃身所在层数，⼀个失败结点的查找⻓度 = 其⽗结点所在层数默认情况下，各种失败情况或成功情况都等概率发⽣。由n个结点划分出共有n+1种查找失败的情况。上图中，方形是失败结点，圆形是成功结点。

• 查找成功：
  ${ASL}_s=\frac{1+2+3+...+n}{n}=\frac{n+1}{2}$

• 查找失败：
  ${ASL}_f=\frac{1+2+3+...+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$
  对比之前的查找效率，查找成功长度不变，但是查找失败长度缩减近一半。

3. 顺序查找的优化（被查概率不相等）

对于被查概率不相等时，被查概率⼤的放在靠前位置s，这样查找成功时候 $ASL$ 更少。

[79] 折半查找

1.查找过程推演

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

1. 起始状态，low、high分别指向头位序、尾位序的元素，mid 指向中间元素，开始查找。
2. 对比target和mid所指元素的值，发现target > a[mid]，锁定目标一定位于右半边。

3. low移至mid的下一位，mid更新。
4. 对比target和mid所指元素的值，发现target < a[mid]，锁定目标一定位于左半边。

5. high移动至mid的前一位，mid更新。
6. 对比target和mid所指元素的值，发现target > a[mid]，锁定目标一定位于右半边。

7. low移至mid的下一位，mid更新。
8. 对比target和mid所指元素的值，发现target == a[mid]，查找成功。

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

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值
}

注意，在查找失败的时候，low、high指针均在mid的基础上加1或者减1，因为在上一轮的判定过程中，已经排除mid位置与target不符合，所以，可以直接跳过该序列。另外，如果顺序表时降序排列，代码的逻辑需要重新修改。

2.查找效率分析，使用判定树

以上查找分析查找过程，画查找判定树：

• 查找成功判定树：

$${ASL}_s=\frac{1+2\times 2+3\times 4+4\times 4}{11}=3$$

• 查找失败判定树：

$${ASL}_f=\frac{3\times 4+4\times 8}{12}=3.67$$

3. 查找判定树的构造

• 如果当前，low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等（根结点占据一个）。
• 如果当前，low和high之间有偶数个元素，则 mid 分隔后，左半部分比右半部分少⼀个元素（由于根结点mid向下取整）。

因此，折半查找的判定树中，若 $mid=\lfloor (low+high)/2\rfloor$ ，则对于任何⼀个结点，必有：

右子树结点数 - 左子树结点数 =0 或 1

所以，根据平衡二叉树（AVL）定义，折半查找的判定树⼀定是平衡⼆叉树。在折半查找的判定树中，只有最下⾯⼀层是不满的。树高： $h=\lceil {\log }_2(N+1)\rceil$ 这里的树⾼不包含含失败结点。

判定树结点关键字：左 < 中 < 右，同时，满⾜⼆叉排序树（BST）的定义。 所以，二分查找是综合了二叉排序树和平衡二叉树的一种算法。

4. 查找效率分析

N个结点，将区间段划分成N + 1个，因此失败结点：N +1 个，等于成功结点的空链域数量。
在判定树的前提下，查找成功的 $AS{L}_s\le h$ , 查找失败的 $AS{L}_f\le h$ 。
因此，折半查找的时间复杂度为 $O({\log }_{2}N)$ 。