5. 查找

ABSTRACT · 本节范围 本笔记逐页覆盖原 PDF 的 7 页、7 道代码题：有序表查找/交换/插入、单链表结点前移、递归与非递归折半查找、BST 合法性、BST 最值、BST 结点层次、输出所有大于关键字的结点。代码统一为 C++17，原稿的查找方向、返回值、空表和空树语义均已订正。

0. 公共定义

#include <algorithm>
#include <cstddef>
#include <limits>
#include <optional>
#include <utility>
#include <vector>

struct LNode {
    int data{};
    LNode* next = nullptr;
};

struct BSTNode {
    int data{};
    BSTNode* left = nullptr;
    BSTNode* right = nullptr;
};

• 顺序表和向量下标统一从 0 开始，查找失败返回 -1。
• BST 采用严格次序：左子树关键字 $<$ 根关键字 $<$ 右子树关键字，不允许重复关键字。
• BST 根结点层号为 1；空树合法，空树没有最大值、最小值或结点层号。

1. 有序顺序表：查找后交换，否则插入

1.1 题目

顺序表严格递增。以尽可能低的时间复杂度查找 $x$：

• 若找到且它有后继元素，将它与后继交换；
• 若找到但它已是表尾，不交换；
• 若未找到，按递增次序插入 $x$。

1.2 算法

先用折半思想求第一个“不小于 $x$”的位置 pos。若该位置等于 $x$，执行相邻交换；否则 pos 正是插入位置。

std::size_t lowerBoundIndex(const std::vector<int>& values, int x) {
    std::size_t low = 0;
    std::size_t high = values.size();  // 半开区间 [low, high)
    while (low < high) {
        const std::size_t mid = low + (high - low) / 2;
        if (values[mid] < x) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

void findSwapOrInsert(std::vector<int>& values, int x) {
    const std::size_t position = lowerBoundIndex(values, x);
    if (position < values.size() && values[position] == x) {
        if (position + 1 < values.size()) {
            std::swap(values[position], values[position + 1]);
        }
        return;
    }
    values.insert(values.begin()
                      + static_cast<std::ptrdiff_t>(position), x);
}

查找为 $O(\log n)$；找到时交换为 $O(1)$，未找到时顺序表移动元素不可避免，插入最坏为 $O(n)$。

WARNING · 操作后的有序性 当 $x$ 与更大的后继交换后，局部次序变成“后继、$x$”，顺序表不再递增。这是题目明确要求的结果，因此本算法不能在不重新排序的情况下连续依赖原有序性再次执行。

DANGER · 原稿错误 原稿在空表或查找失败时仍可能读取未初始化的 mid；插入循环的下标在循环后使用也不清楚。半开区间写法直接得到合法插入位置，空表同样成立。

2. 单链表目标结点与前驱交换

2.1 题目与边界

带头结点单链表中，找到第一个值为 key 的数据结点，将它与前一个数据结点交换。若目标是首元结点或不存在，则无法交换，返回 false。

2.2 可运行实现

bool swapWithPredecessor(LNode* head, int key) {
    if (head == nullptr || head->next == nullptr) {
        return false;
    }

    LNode* beforePrevious = head;
    LNode* previous = head->next;
    if (previous->data == key) {
        return false;  // 首元结点没有数据前驱。
    }

    LNode* current = previous->next;
    while (current != nullptr && current->data != key) {
        beforePrevious = previous;
        previous = current;
        current = current->next;
    }
    if (current == nullptr) {
        return false;
    }

    previous->next = current->next;
    current->next = previous;
    beforePrevious->next = current;
    return true;
}

时间复杂度 $O(n)$，辅助空间 $O(1)$。交换尾结点同样成立。

DANGER · 原稿错误 原稿在空表、单结点表上会直接解引用 list->next 或 list->next->next；遍历与交换后的判断还会把“找到最后一个结点”误判为失败。

3. 折半查找：非递归与递归

3.1 前提与区间

数组必须递增并支持随机访问。闭区间 [low, high] 有效时条件为 low <= high；失败条件为 low > high。

3.2 可运行实现

int binarySearch(const std::vector<int>& values, int key) {
    int low = 0;
    int high = static_cast<int>(values.size()) - 1;
    while (low <= high) {
        const int mid = low + (high - low) / 2;
        if (values[mid] == key) {
            return mid;
        }
        if (values[mid] < key) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int binarySearchRecursiveImpl(const std::vector<int>& values,
                              int key,
                              int low,
                              int high) {
    if (low > high) {
        return -1;
    }

    const int mid = low + (high - low) / 2;
    if (values[mid] == key) {
        return mid;
    }
    if (values[mid] < key) {
        return binarySearchRecursiveImpl(
            values, key, mid + 1, high);
    }
    return binarySearchRecursiveImpl(
        values, key, low, mid - 1);
}

int binarySearchRecursive(const std::vector<int>& values, int key) {
    return binarySearchRecursiveImpl(
        values, key, 0, static_cast<int>(values.size()) - 1);
}

两种方法时间均为 $O(\log n)$；非递归辅助空间 $O(1)$，递归调用栈 $O(\log n)$。

DANGER · 原稿错误 原稿在 values[mid] > key 时错误地令 low = mid + 1，在 values[mid] < key 时又缩小右边界，方向完全相反；递归版还没有返回递归调用结果，并存在函数声明为 void 却返回整数等语法错误。

4. 判断一棵树是否为 BST

4.1 全局约束

仅比较“当前结点与直接孩子”不够，因为 BST 要求左子树所有关键字都小于根、右子树所有关键字都大于根。递归传递当前结点允许的开区间 $(lower, upper)$：

• 左子树上界收紧为当前值；
• 右子树下界收紧为当前值。

4.2 可运行实现

bool isBSTImpl(const BSTNode* root,
               long long lower,
               long long upper) {
    if (root == nullptr) {
        return true;
    }
    if (root->data <= lower || root->data >= upper) {
        return false;
    }
    return isBSTImpl(root->left, lower, root->data)
        && isBSTImpl(root->right, root->data, upper);
}

bool isBST(const BSTNode* root) {
    return isBSTImpl(
        root,
        std::numeric_limits<long long>::lowest(),
        std::numeric_limits<long long>::max());
}

时间 $O(n)$，递归栈 $O(h)$。使用 long long 边界使合法的 INT_MIN、INT_MAX 结点不会与哨兵冲突。

DANGER · 原稿错误 原稿使用全局 pre = -INT_MAX：它不是 INT_MIN，会错误拒绝最小整型关键字；全局状态在多次调用前若不重置，也会让后一次判断受到前一次影响。

5. BST 的最小值与最大值

BST 最小结点是沿左孩子走到尽头的结点，最大结点是沿右孩子走到尽头的结点。空树返回空指针，不能返回整数 0，因为 0 可能是合法关键字。

const BSTNode* minimumNode(const BSTNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    while (root->left != nullptr) {
        root = root->left;
    }
    return root;
}

const BSTNode* maximumNode(const BSTNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    while (root->right != nullptr) {
        root = root->right;
    }
    return root;
}

时间复杂度 $O(h)$，辅助空间 $O(1)$。

6. 求指定结点在 BST 中的层次

沿 BST 查找路径移动，每下降一层将层号加 1；命中时返回层号，不存在时返回 -1。

int bstLevel(const BSTNode* root, int key) {
    int level = 1;
    while (root != nullptr) {
        if (root->data == key) {
            return level;
        }
        root = key < root->data ? root->left : root->right;
        ++level;
    }
    return -1;
}

时间 $O(h)$，辅助空间 $O(1)$。原稿命中后错误地返回 key，并对未声明变量 n 自增，因而没有真正返回层号。

7. 输出 BST 中所有大于 key 的结点

为了按递增次序输出，采用中序顺序。若当前值不大于 key，它的整棵左子树也不可能满足条件，可直接剪枝，只搜索右子树。

void collectGreaterThan(const BSTNode* root,
                        int key,
                        std::vector<int>& result) {
    if (root == nullptr) {
        return;
    }
    if (root->data <= key) {
        collectGreaterThan(root->right, key, result);
        return;
    }

    collectGreaterThan(root->left, key, result);
    result.push_back(root->data);
    collectGreaterThan(root->right, key, result);
}

std::vector<int> greaterThan(const BSTNode* root, int key) {
    std::vector<int> result;
    collectGreaterThan(root, key, result);
    return result;
}

设输出结点数为 $k$，平衡 BST 中可做到 $O(h+k)$；最坏退化树仍为 $O(n)$。原稿无条件遍历左右子树，虽然结果正确，但没有利用 BST 次序剪枝。

8. 七题覆盖与纠错速查

相关知识

• 科目导航：数据结构导航
• 阅读顺序：上一篇：二叉树代码 · 下一篇：图代码
• 关联专题：查找原理

9. 本节复盘

• 折半查找的核心不是背代码，而是始终维护“答案仍在当前区间内”的不变式。
• 顺序表查找可为 $O(\log n)$，但中间插入仍需移动元素，最坏 $O(n)$。
• 链表交换相邻结点需要同时保存前前驱、前驱和当前结点。
• BST 判断传递的是祖先给出的全局范围，不能只比较父子。
• BST 的极值、层次和范围输出都应利用“左小右大”剪枝。