数据结构之查找绪论

概念

1) 查找

查找是指在数据集合中寻找满足某种条件的数据元素的过程。查找结果有两种：

查找成功：在集合中找到了满足条件的元素。
查找失败：未找到满足条件的元素。

2) 查找表（查找结构）

查找表是用于查找的数据集合，包含同一类型的数据元素（或记录）。常见的操作有：

查询：判断某个数据元素是否存在。
检索：获取某数据元素的属性。
插入：将新的数据元素插入到表中。
删除：从表中移除数据元素。

3) 静态查找表与动态查找表

静态查找表：操作仅涉及查询和检索，不需要修改数据。适合的查找方法包括：顺序查找、折半查找、散列查找等。
动态查找表：需要动态插入或删除数据。适合的查找方法包括：二叉排序树查找、散列查找等。常见的改进结构有二叉平衡树和B树。

4) 关键字

关键字是数据元素中唯一标识该元素的某个数据项。例如，学生元素中的“学号”是唯一标识一名学生的关键字。

5) 平均查找长度（ASL）

平均查找长度（ASL）衡量查找算法的效率，定义为：

$ ASL = P_i C_i $

其中：

$n$：查找表长度。
$P_i$：查找第$i$个元素的概率，若查找概率相等，则 $P_i = \frac{1}{n}$。
$C_i$：找到第$i$个元素所需的比较次数。

平均查找长度反映了查找算法的效率。

顺序查找（线性查找）

1. 一般线性表的顺序查找

顺序查找是一种从线性表的一端开始，逐个检查每个元素的关键字是否满足给定条件的查找方法。适用于无序的顺序表和链表。

基本思想：

从线性表的首端开始，逐个检查元素的关键字。
若某元素的关键字满足条件，则查找成功，返回该元素的位置。
若查找到表的末端仍未找到符合条件的元素，则返回查找失败。

算法引入"哨兵"优化： 在顺序查找算法中，可以引入“哨兵”元素，避免判断是否越界，提高效率。哨兵的作用是使得查找过程中不必每次都检查数组是否越界。

平均查找长度 (ASL) 分析：

查找成功时，若每个元素的查找概率相等，平均查找长度为： $ ASL_{} = $
查找失败时，比较次数为 $n+1$，不成功时的平均查找长度为： $ ASL_{} = n + 1 $

优缺点：

优点： 适用于无序线性表，存储结构没有要求，顺序存储或链式存储都可以应用。
缺点： 当表的规模较大时，平均查找长度较大，效率低下。

2. 有序表的顺序查找

若线性表中的元素按关键字有序排列，可以在查找时利用这一特性，减少不必要的比较。

优化思想：

若查找到某元素时，该元素的关键字小于目标值，而下一元素的关键字大于目标值，则可以直接返回查找失败。
这样可避免继续比较剩余的元素，从而减少查找失败时的比较次数。

查找过程的判定树：

判定树用于描述有序线性表的查找过程，圆形节点表示表中的元素，矩形节点为失败结点，表示查找失败时的位置。

查找失败时的平均查找长度：

查找失败时，平均查找长度为： $ ASL_{} = + $ 当 $n = 6$ 时，查找失败的平均长度约为 3.86，比一般无序表的顺序查找更优。

注意事项：

有序表的顺序查找和折半查找不同，有序表的顺序查找仍然是逐个比较，而折半查找通过二分法缩小查找范围。

折半查找（又称二分查找）

基本思想

折半查找适用于有序的顺序表。其基本思想是：首先将待查找的值 $key$ 与表中间位置的元素进行比较，若相等，则查找成功，返回该元素的存储位置；若不相等，则根据 $key$ 大小确定要查找的范围是中间元素之前还是之后的一半。重复这个过程，直到找到该元素或确定元素不存在。若查找失败，返回失败信息。

算法实现

int BinarySearch(SeqList 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; // 查找失败
}

查找过程示例

已知有序表 $ {7, 10, 13, 16, 19, 29, 32, 33, 37, 41, 43} $，以查找 $key = 11$ 为例：

第一次查找：
中间位置元素为 $29$，因为 $11 < 29$，所以查找范围缩小为前半部分 $[low, mid-1]$，即 $[7, 10, 13, 16, 19]$。更新 $high = mid - 1 = 5$。
第二次查找：
中间位置元素为 $13$，因为 $11 < 13$，查找范围继续缩小为 $[7, 10]$。更新 $high = mid - 1 = 2$。
第三次查找：
中间位置元素为 $10$，因为 $11 > 10$，查找范围缩小为 $[10, 13]$。更新 $low = mid + 1 = 2$。
第四次查找：
查找范围只有一个元素 $10$，且不等于 $11$，故查找失败。