集合和搜索

集合的抽象数据类型

集合结构之间无关系

常见集合实现

线性表、搜索树、散列表

顺序搜索

%%{init: {"flowchart": {"htmlLabels": false}} }%%
flowchart LR
a["线性表"]
b["有序表（元素按关键字值的大小次序排列）"]
c["无序表"]
a --> b
a --> c

无序表的顺序搜索

从第一个元素开始，将待查元素 x 的关键字与表中关键字一一比较

• 找到即止
• 遍历全部没找到才停

有序表的顺序搜索

从头开始，将待查元素 x 与表中关键字进行比较

• 找到即止
• 搜索到某元素关键字大于 x 的关键字时，搜索失败，停止

有哨兵的顺序搜索方法

有序表最后添加一个无穷大的数

作用

简化循环条件判断，不需要检查数组是否越界，一定程度地提升搜索速度

二分搜索

• 表长 <= 0，返回
• 根据算法选取分割点 a_m 与 x 进行比较
  • a_m.key = x.key，搜索成功
  • a_m.key >或< x.key，继续二分搜索

对半搜索

二分搜索的一种，分割点为中点元素

$$
m=\frac{(low+high)}{2}
$$

若有序表表长为偶数，默认取前一个元素

对半搜索示例

查找 key=66 的元素

在第三趟搜索时，并不会直接得出结果，还需要进行一次比较

比较 对半 和 顺序，不管是成功还是失败，对半都更快一些

关键代码（使用迭代的方式可以一定程度上减少资源消耗）：

// 二分查找函数
int binarySearch(const vector<int>& arr, int target) {
    if (arr.empty()) return -1; // 边界检查

    size_t left = 0;                 // 数组的左边界
    size_t right = arr.size() - 1;   // 数组的右边界

    while (left <= right) {
        size_t mid = left + (right - left) / 2; // 计算中间索引

        if (arr[mid] == target) {
            return static_cast<int>(mid);  // 找到目标值，返回索引
        }
        else if (arr[mid] < target) {
            left = mid + 1;  // 目标值在右半部分
        }
        else {
            right = mid - 1;  // 目标值在左半部分
        }
    }
    return -1;  // 如果没有找到目标值，返回-1
}

C++ 标准库提供了 std::lower_bound 函数，可以直接用于二分查找，减少手动实现的工作量

#include <iostream>
#include <vector>
#include <algorithm> // 用于 std::lower_bound
using namespace std;

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int target = 7;

    auto it = lower_bound(arr.begin(), arr.end(), target);
    if (it != arr.end() && *it == target) {
        cout << "目标值 " << target << " 索引为: " << distance(arr.begin(), it) << endl;
    } else {
        cout << "目标值 " << target << " 不在数组中。" << endl;
    }
    return 0;
}

平均搜索长度分析（ASL）

平均搜索长度：为了确定一个指定关键字值的记录在表中的位置，对关键字值之间比较次数的期望值

无序表的顺序搜索

（1）成功搜索的平均搜索长度

表中元素 a_i 被搜索的概率 p_i ，每个元素的搜索概率相等（p_i=1/n），则

$$
ASL_S=\sum^n_{i=1}i\times p_i=\frac{1}{n}\sum^n_{i=1}i=\frac{n+1}{2}
$$

（2）搜索失败的平均搜索长度

总共 n 次关键字值的比较

$$
ASL_F=n
$$

有序表的顺序搜索

（1）成功搜索的平均搜索长度

同无序表

$$
ASL_S=\sum^n_{i=1}i\times p_i=\frac{1}{n}\sum^n_{i=1}i=\frac{n+1}{2}
$$

（2）搜索失败的平均搜索长度

比无序时快约一倍

$$
ASL_F=1+\sum^{n+1}_{i=1}i\times\frac{1}{n+1}=2+\frac{n}{2}
$$

对半搜索

平均时间复杂度

$$
O(log_2n)
$$

（1）成功搜索的平均搜索长度

量级与平均时间复杂度相同

以根结点为 1，下一层结点均加一，只计算内结点（不算叶结点）

$$
ASL_s=\frac{\sum i}{\sum n}，其中i为结点标记数，n为结点数
$$

（2）搜索失败的平均搜索长度

只计算外结点（叶结点）

$$
ASL_s=\frac{\sum i}{\sum n}，其中i为外结点标记数，n为外结点数
$$