数组查找

真题练习：可在站内题库按“数组查找”知识点筛选。

在选择题中偶会考查，内容也不算难，关键在于掌握算法思想，也许会在算法设计题中间接考察到。

顺序查找

顺序查找的 核心思想 是从数组（线性表）的第一个元素开始，逐个检查每个元素是否等于目标值，直到找到目标或检查完整个数组。

其代码实现如下，非常简单，遍历一次数组即可：

int SequentialSearch(int A[], int n, int value) {
    for (int i = 0; i < n; i++) {
        if (A[i] == value) {
            return i;  // 找到，返回索引
        }
    }
    return -1;  // 未找到
}

顺序查找的 时间复杂度 如下：

• 最好情况：$O(1)$
• 最坏情况：$O(n)$
• 平均情况：$O(n)$

折半查找

折半查找 要求数组是有序的。

其 核心思想 在于每次将查找范围折半，只保留目标可能存在的一半，直到范围为空或找到目标为止。

例如，在有序数组中查找一个元素时，可以先比较中间元素：

• 如果目标值小于中间值，查左半部分；
• 如果目标值大于中间值，查右半部分；
• 如果相等，则查找成功。

下面以有序数组中查找元素 23 为例。为避免 $low+high$ 溢出，中点下标可写成

---

折半查找可以基于 迭代实现，也可以作为一个 递归函数实现：

• 迭代版
• 递归版

int BinarySearch(int A[], int n, int value) {
    int low = 0;
    int high = n - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;  // 防止溢出

        if (A[mid] == value) {
            return mid;  // 找到
        } else if (A[mid] < value) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;  // 未找到
}

int BinarySearchRecursive(int A[], int low, int high, int value) {
    if (low > high) {
        return -1;  // 区间无效，查找失败
    }

    int mid = low + (high - low) / 2;

    if (A[mid] == value) {
        return mid;  // 找到目标
    } else if (A[mid] < value) {
        return BinarySearchRecursive(A, mid + 1, high, value);  // 查右半部分
    } else {
        return BinarySearchRecursive(A, low, mid - 1, value);   // 查左半部分
    }
}

折半查找的 时间复杂度 如下：

• 最好情况：$O(1)$
• 最坏情况：$O(\log_2 n)$
• 平均情况：$O(\log_2 n)$

折半查找判定树

折半查找判定树（Binary Search Decision Tree）是折半查找（Binary Search）过程的树形表示，用于清晰地 描述在查找过程中所做的每一次比较决策。

所以简单地来说，如何根据一个有序序列得到一个折半查找判定树呢，就是将折半查找的过程走一遍，举两个实际的例子来说明一下：

假设数组为 [10, 20, 30, 40, 50, 60]，元素个数为 6。

🌳 折半查找判定树构造原则

折半查找需要选一个“中点”作为根节点。偶数长度数组有两个中点，一般可以：

• 选靠左的那个（常见做法）：mid = (low + high) // 2
• 或者选靠右的那个

假设按 常规左中点 来构造，则 构造过程如下：

1. [10, 20, 30, 40, 50, 60]，mid = 2 → 30 为根；

2. 左边 [10, 20]，mid = 0 → 10 为左子树；

   • 右边是 [20] → 作为 10 的右子节点；

3. 右边 [40, 50, 60]，mid = 4 → 50 为右子树；

   • 左边 [40] → 左子节点；
   • 右边 [60] → 右子节点。

最后可以得到如下折半查找判定树：

分块查找

线性表的 分块查找 通常应用于一种特定的情境：线性表（例如数组）被分为多个大小相等（或者最后一个块可能较小）的块，并且块内的元素是无序的，但是块与块之间是有序的。也就是说，每个块内的最大（或最小）元素小于下一个块的任意元素。

常用的 分块查找策略 如下：

1. 先对块索引进行顺序或二分查找以确定所需元素可能所在的块。
2. 然后在确定的块中进行顺序查找。

若长度为 $n$ 的线性表被均匀分成 $b$ 块，每块约有 $s$ 个元素，且索引表使用顺序查找，则平均比较次数量级为

当 $b\approx s\approx \sqrt n$ 时，查找长度约为 $O(\sqrt n)$。若索引表使用折半查找，则确定块的代价可降为 $O(\log b)$，但块内仍需顺序查找。

查找失败与重复关键字

折半查找终止时若 low 已经大于 high，表示候选区间已经为空，目标不在当前有序表中；这也是代码不能把循环条件写成“low 小于 high”的原因，否则最后只剩一个候选元素时会被漏查。若表中允许重复关键字，普通折半查找找到的是某个匹配位置，并不保证是第一个或最后一个；要找第一个匹配位置，应在命中后继续向左收缩区间，要找最后一个则继续向右收缩。

顺序查找对重复关键字通常天然返回第一个遇到的位置，分块查找则还要保证块间的边界条件与索引项定义一致。题目没有说明重复关键字的处理规则时，不应擅自把“找到任意一个”和“定位首次出现”当作同一种要求。