企业官网建设流程全解析

开头

写这篇笔记之前，我其实已经把这一part的内容反复看了三遍。原因很简单：有序表归并、二分查找、二叉搜索树查找这三个主题，表面上看是三个独立的知识点，实际在数据结构的学习里是同一根藤上结出来的瓜——它们都在解决“怎么在一片数据里快速找到目标”，区别只是数据组织方式不同、查找策略不同。尤其是对考研党、期末复习党和刚转行刷算法的人，这三个点几乎每次考试和面试都会被拎出来单考，但很少有人告诉你它们内部的联系和边界条件为什么要这么抠。

这篇文章就把这三个东西放在一起做一个整合笔记，包含核心思路、可复现代码、复杂度分析、常见坑点，以及我实际刷题和复习时踩过的雷。适合正在学《数据结构》这门课的学生、准备面试的开发者，以及想系统过一遍查找算法的朋友。看完你应该能达到这样一个效果：给你一道题，你能快速判断该用有序表归并、二分查找还是二叉搜索树，并且边界条件不再靠猜。

1. 为什么把这三个主题放在一起学

1.1 三个主题的关联点：都建立在“有序”之上

先理清逻辑。有序表归并解决的是“把两个已经有序的序列合成一个依然有序的序列”，二分查找解决的是“在一个已经有序的序列里快速定位目标值”，而二叉搜索树查找解决的是“在一棵满足左小右大的树结构里快速定位目标值”。你看，三者的前提条件全部指向同一个词——有序。

这个关联不是巧合。很多初学者会以为二叉搜索树和二分查找是两套完全独立的东西，实际上二叉搜索树的查找过程，本质上就是在执行一种“二叉化”的二分查找：每次比较后丢弃一半子树，跟二分查找每次比较后丢弃一半区间是同一个逻辑。区别在于，二分查找的底层是连续存储（数组），支持随机访问，所以可以直接用下标算中点；二叉搜索树的底层是链式存储（节点和指针），没有随机访问能力，所以用树的分支结构来模拟“丢弃一半”的过程。

我在复习的时候把三个主题串成一条线，效果比分开记好得多。推荐你也这样学。

1.2 学习路径怎么安排最省力

建议顺序是：有序表归并 → 二分查找 → 二叉搜索树查找。理由有两点。

第一，归并是最直观的入门。它只涉及线性扫描和指针移动，不需要复杂的递归思维，也不需要理解循环不变量。把归并写顺了，你对“指针/下标移动控制循环”这件事就有了手感，这个手感是二分查找和二叉树遍历共用的基础能力。

第二，二分查找可以作为“数组版查找”的收官，二叉搜索树作为“链表版查找”的进阶。二分查找的难点在于区间定义和边界更新，二叉搜索树的难点在于递归理解和树形结构的状态维护。一个偏重“循环细节”，一个偏重“递归结构”，用这个顺序学，思维难度是逐步抬升的，不会一上来就被递归整懵。

注意：不要一上来就试图背代码模板。边界条件这种东西，背得快忘得也快，必须理解区间定义之后自己推导一遍，才能应变各种变种题。

2. 有序表归并：最容易被忽视的基础功

2.1 归并的核心思想与适用场景

有序表归并，简单说就是有两个已经各自排好序的线性表（通常是数组），把它们合并成一个整体有序的线性表。经典的归并排序中，Merge 操作就是干这件事的，所以它也是归并排序的核心子过程。

为什么说它容易被忽视？因为很多教材把这部分放在“线性表”章节里一笔带过，学生也觉得“不就是把两个数组接起来再排序吗”。我刚开始也有这个想法，直到做数据结构实验时才明白，这个操作的关键约束是：要求时间复杂度 O(m+n)，不能直接用排序算法重排。也就是说，你必须利用两个输入序列本身有序这个条件，用线性扫描完成合并。

适用场景非常广：归并排序、多路归并外部排序、合并两个有序链表、K 个有序数组合并的简化版，甚至数据库里多路归并的思想源头都在这里。面试里很多链表题也喜欢考“合并两个有序链表”，本质就是有序表归并的链表版。

2.2 数组版归并的代码实现与参数选择

数组版归并的核心思路是用两个指针分别指向两个数组的当前位置，每次比较两个指针指向的元素，把较小的放入结果数组，然后移动对应指针，直到某个数组扫描完，再把另一个数组剩余部分全部拷贝过去。

下面这个写法是我在实验中验证过的，比较典型的三个指针版本：

// 合并两个有序数组 arr1[0..m-1] 和 arr2[0..n-1]，结果存入 mergeArr void mergeArray(int arr1[], int m, int arr2[], int n, int mergeArr[]) { int i = 0, j = 0, k = 0; // 同时扫描两个数组，谁小谁进结果数组 while (i < m && j < n) { if (arr1[i] <= arr2[j]) { mergeArr[k++] = arr1[i++]; } else { mergeArr[k++] = arr2[j++]; } } // 当 arr2 扫描完时，把 arr1 剩余部分拷贝进去 while (i < m) { mergeArr[k++] = arr1[i++]; } // 当 arr1 扫描完时，把 arr2 剩余部分拷贝进去 while (j < n) { mergeArr[k++] = arr2[j++]; } }

这里有个细节值得单独说：mergeArr的空间必须由调用方事先分配足够大（至少 m+n），函数内部不能假设数组够大，否则写越界就是经典的内存错误。这在 C 语言里尤其关键，C++ 用 vector 可以规避一部分风险，但底层逻辑完全一样。

另一个细节是<=和<的选择。用<=可以保证当两个元素相等时优先取前一个数组的元素，这是归并排序稳定性的来源。如果改成<，两个数组的相等元素顺序会交换，导致归并排序不稳定。在做不需要稳定性的场景下两种写法都对，但如果你在实现归并排序并且要求稳定，必须写成<=。

链表版的有序表归并逻辑上完全一致，只是把数组下标换成指针移动，递归写法里常见的“虚拟头节点”技巧可以省去大量空指针判断，建议实习时优先用虚拟头节点。

2.3 归并的复杂度、边界条件与易错点

时间复杂度是 O(m+n)，因为两个数组各被扫描一次；空间复杂度是 O(m+n)，因为需要额外的结果数组。如果是链表版原地合并，空间复杂度可以做到 O(1)。

实际写代码最容易翻车的三个地方：

1. 循环结束后的剩余元素处理写漏。两个主循环结束后，必定有一个数组还剩元素，两个 while 拷贝语句必须都写上。有些人只写一个，测试用例恰好第一个数组先空就过了，换一组数据立刻崩。

2. 结果数组的下标 k 自增顺序写错。mergeArr[k++] = arr1[i++]这句话里 k 的自增必须放在赋值之后，写成mergeArr[k] = arr1[i]; k++; i++;等价，但不要写成mergeArr[++k]，否则第一个元素会写到下标 1，下标 0 变成未初始化的脏数据。

3. 输入数组本身不是有序的。有序表归并的前提是两个输入有序，如果调用方传入无序数组，结果必然错误。严谨的做法是在函数注释里明确前置条件，或者在测试前用断言检查。

我自己的习惯是：写完归并函数后，先用三个用例自测——两个等长数组、一个数组为空、两个数组长度悬殊。这三个用例跑通，基本能覆盖所有边界。

3. 二分查找：边界条件决定生死

3.1 二分查找的原理与“循环不变量”

二分查找的思路一句话就能说清：在一个有序数组里，每次取中间位置的元素跟目标值比较，等于直接返回，小于则搜索右半部分，大于则搜索左半部分，直到区间为空为止。每次比较都能排除一半数据，所以时间复杂度 O(log n)。

但这句话的“直到区间为空为止”在代码里怎么表达，就是所有初学者痛苦的来源。写法五花八门：while (left < right)还是while (left <= right)？更新区间时right = mid还是right = mid - 1？为什么有时候死循环有时候漏元素？

要彻底解决这个问题，必须引入“循环不变量”的概念。所谓循环不变量，就是你在整个循环过程中始终维护的一个定义。我跟学生讲的时候喜欢用“你定义的搜索区间是什么”来问他们：

• 如果你定义搜索区间是闭区间[left, right]，那么left和right指向的元素都还没被检查过，所以循环条件是while (left <= right)，因为区间内至少有一个元素时就需要继续。更新时，mid已检查过，所以下次区间要么是[left, mid-1]，要么是[mid+1, right]。
• 如果你定义搜索区间是左闭右开[left, right)，那么right指向的元素已经被排除在外，循环条件是while (left < right)，更新时right = mid（因为 mid 已经被检查过，且右边界是开区间，所以可以直接取 mid），left = mid + 1。

这两种定义都对，但你必须自始至终只遵守一种，混着写必然出错。这就是我反复强调“循环不变量”的原因——它不是考试术语，而是你写代码时心里的那根准绳。

3.2 标准二分查找模板（含查找第一个/最后一个等于目标值的变种）

先给最经典的闭区间版本：

// 在升序数组 nums 中查找 target，找到返回下标，找不到返回 -1 int binarySearch(int nums[], int size, int target) { int left = 0, right = size - 1; // 闭区间 [left, right] while (left <= right) { int mid = left + (right - left) / 2; // 防止溢出 if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; // target 在右半部分 } else { right = mid - 1; // target 在左半部分 } } return -1; }

注意mid的计算方式。(left + right) / 2在 left 和 right 都很大时可能整型溢出，left + (right - left) / 2可以避免这个问题。虽然考试题一般不考这个，但实际工程代码里溢出就是线上事故，养成习惯是值得的。

二分查找在实际面试里经常考变种：查找第一个等于 target 的下标、查找最后一个等于 target 的下标、查找第一个大于等于 target 的下标。网上流传的模板很多，我给一个我自己整理的左闭右开版本，用同一个模板统一解决：

// 在 [left, right) 中找第一个 >= target 的下标 int lowerBound(int nums[], int size, int target) { int left = 0, right = size; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; }

基于lowerBound，你可以轻松实现：

• 第一个等于 target：idx = lowerBound(nums, size, target)，检查nums[idx] == target即可。
• 第一个大于 target：lowerBound(nums, size, target + 1)。
• 最后一个等于 target：lowerBound(nums, size, target + 1) - 1，再检查合法性。

一次记住一个核心函数，其他变种都在它上面推导，比背四五个不同模板靠谱太多。这是我最想让你带走的一个实操技巧。

3.3 二分查找死循环与漏解的实时排查

写二分查找最容易出的问题就是死循环和漏解。死循环的表现是程序卡住不退出，漏解的表现是明明数组里有 target 却返回 -1。

我用一个很笨但很有效的调试方法：拿小数组手动推演。比如nums = [1, 3, 5, 7, 9],target = 5，逐行按照代码走一遍，把每次循环的 left、right、mid 都写出来。走完一遍基本就能发现自己哪一步边界写错了。

第二个实用技巧是在循环里打印三个变量的值。如果发现某次循环里left和right没有变化，那一定是有个分支没更新。常见情况是mid计算向下取整，导致left = mid时区间永远不缩小，死循环。解决方式是：当left = mid时，mid 计算要向上取整，即mid = left + (right - left + 1) / 2。

第三，如果题目要求的是“最后一个小于等于 target 的元素”，且你用了左闭右开模板，建议多测几个 target 不在数组内、target 小于所有元素、target 大于所有元素这三类边界。很多漏解是在这些极端输入下才暴露的。

我把这些经验写进代码注释里之后，再回看半年前自己写的二分，真的是惨不忍睹。总之，二分查找的调试没有捷径，耐心推演几遍，你就能形成肌肉记忆。

4. 二叉搜索树查找：递归思维的试金石

4.1 二叉搜索树的结构定义与查找原理

二叉搜索树（Binary Search Tree，BST）是这么一棵二叉树：对于任意节点，它的左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值，且左右子树本身也都是二叉搜索树。

这个定义非常简洁，但你要仔细把它跟普通二叉树区分开。普通二叉树对节点值没有任何要求，所以查找只能遍历；BST 因为有了大小约束，查找时就能像二分查找那样，每走一步丢弃一棵子树。

查找过程的自然语言描述是：从根节点开始，如果当前节点为空说明没找到；如果当前节点的值等于 target，返回该节点；如果 target 小于当前节点值，递归去左子树找；如果 target 大于当前节点值，递归去右子树找。递归版本的代码量极少，我写在这里：

// 二叉搜索树节点定义 typedef struct BSTNode { int data; struct BSTNode *left; struct BSTNode *right; } BSTNode; // 递归实现查找 BSTNode* bstSearch(BSTNode* root, int target) { if (root == NULL || root->data == target) { return root; } if (target < root->data) { return bstSearch(root->left, target); } else { return bstSearch(root->right, target); } }

递归写法的核心是“出口条件”和“递归调用”。出口条件有两个：节点为空，返回空；节点值命中，返回节点。递归调用就是根据当前节点值和 target 的大小关系，选择去左还是去右。

4.2 递归版 vs 迭代版：各自的优劣与适用场景

递归版看起来优雅，但有两个隐患：一是递归深度受系统栈大小限制，如果树退化成链（比如按有序序列插入节点导致 BST 变成一个单链表），查找时递归深度可能达到 n，极端情况下爆栈；二是递归调用有一定函数开销，性能上略逊于迭代。

迭代版用循环代替递归，核心就是让当前节点指针不断下沉：

// 迭代实现查找 BSTNode* bstSearchIter(BSTNode* root, int target) { BSTNode* cur = root; while (cur != NULL && cur->data != target) { if (target < cur->data) { cur = cur->left; } else { cur = cur->right; } } return cur; }

当cur变成 NULL 时，说明已经走到叶子节点的空孩子位置，还没找到，直接返回 NULL。这个版本没有爆栈问题，也更适合工程实际。

我的建议是：初学时两个版本都写一遍。递归版本帮你理解 BST 的递归定义，迭代版本帮你建立循环状态维护的感觉。考试和面试时，通常写递归更简洁，但如果你能写出迭代版，会更显功底。

4.3 BST查找与二分查找的异同

把 BST 查找和二分查找放一起对比，是这本合集最有价值的部分。

相同点：

• 两者都是减治思想：每次比较后丢掉一半候选集，时间复杂度都是 O(log n)（BST 在平衡情况下）。
• 两者都要求数据具有“可比较的序关系”。
• 两者的查找路径都像在走一条从根（或区间中点）到目标（或空区间）的路径。

不同点：

• 存储结构不同。二分查找基于顺序表（数组），支持 O(1) 随机访问；BST 基于链式存储，只能通过指针逐节点移动。
• 插入删除的代价不同。有序数组插入删除都需要搬移元素，O(n)；BST 插入删除只改指针，平均 O(log n)。所以静态数据选二分查找，动态数据选 BST。
• 数据必须提前有序这一点不同。数组要先用排序算法预处理，才能二分查找；BST 在构建过程中就已经维护好有序结构，不需要额外排序，但构建本身也要付出时间成本。

理解这几点，就能明白为什么实际系统里查找往往用平衡树或哈希表而不是纯数组二分——因为现实中几乎没有完全静态的数据集。

4.4 插入和删除对查找性能的连锁影响

BST 查找的效率严重依赖树形。如果一棵 BST 是平衡的，查找 O(log n)；如果节点插入顺序恰好是有序的，树会退化成一条链，查找变成 O(n)。这个退化问题必须提前知道，否则你可能会在实验里莫名其妙超时。

退化根因在于 BST 的形态完全由插入顺序决定，而教材里常规的 BST 插入算法没有自平衡能力。解决办法是引入平衡机制，如 AVL 树、红黑树。它们本质上都是 BST，只是在插入删除后通过旋转操作恢复平衡，从而保证查找稳定在 O(log n)。

作为学习者，我的建议是把 AVL 的四种旋转（LL、RR、LR、RL）当成必学内容，因为面试常问“BST 退化问题你怎么解决”。但如果你只是做课程设计，用一个普通 BST 加随机打乱插入顺序，就已经能保证实际性能了。

5. 三合一实战对比与做题经验

5.1 三种算法适用场景与复杂度速查表

做题目和面试手撕代码时，最关键的能力是在读题后 30 秒内判断该用什么方法。我做了一个速查表，帮助你快速决策：

这张表的结论非常直接：静态数据且需要快速查询，优先二分查找；动态数据且频繁插入删除，优先 BST（或平衡树）；处理多个有序序列，优先归并思路。

5.2 典型题型的破题思路

以我刷题的经验，这三个主题常见的题型大概有这么几类，每类给出破题点。

第一类：合并两个有序数组/链表。这道题几乎就是有序表归并的原题，破题点是“谁小谁先走”，注意链表版用虚拟头节点处理空指针。变种题“合并 K 个有序链表”则要用优先队列（堆），但这已经是高级版本了，初学阶段不用强求。

第二类：在有序数组（或旋转有序数组）中查找目标值。这是二分查找的经典应用。常规数组直接二分；旋转数组需要额外判断哪半部分是有序的，核心是先跟nums[left]比较确定 mid 落在哪个有序区间，再判断 target 在不在这个区间里。

第三类：验证一棵树是不是 BST、在 BST 中查找最近公共祖先。验证 BST 用中序遍历看是否递增，或递归时给每个节点传一个上下界区间。查找 LCA 则利用 BST 特性——如果两个节点都在当前节点左侧，去左子树找；都在右侧，去右子树找；否则当前节点就是 LCA。

第四类：BST 中查找第 k 小的元素。解法是 BST 的中序遍历是升序序列，用中序遍历计数到第 k 个即可。更高效的树形结构是给每个节点维护子树节点数，这个属于进阶，考试很少单独考。

5.3 一套自测题目清单（附难度标记）

在这里收集了 9 道自测题，按难度分三档，适合学完这章后进行自我检验。题目尽量选经典、常见、可验证的：

• 入门档（适合刚学完基础）：

  1. 合并两个有序数组到第三个数组，要求 O(m+n)。难度：低。
  2. 给定有序数组和目标值，返回目标值的下标；不存在返回 -1。难度：低。
  3. 给定一棵二叉树，判断它是否是合法的二叉搜索树。难度：中低。

• 进阶档（适合复习与面试准备）： 4. 在有重复元素的有序数组中，返回目标值第一次出现和最后一次出现的位置。难度：中。 5. 在旋转有序数组中查找目标值，比如 [4,5,6,7,0,1,2] 中找 0。难度：中。 6. 将两个有序链表合并成一个新链表。要求不使用额外数组空间。难度：中。 7. 给定一棵 BST，查找两个节点的最近公共祖先 LCA。难度：中。

• 挑战档（适合冲击高分）： 8. 实现 BST 的删除操作，并保证删除后仍然是 BST。难点在于删除有两个孩子的节点时需要找前驱或后继代替。难度：中高。 9. 用二分查找求一个数的算术平方根的整数部分，不允许使用库函数。难度：中高。

这 9 道题做下来，基本就把三个知识点的核心逻辑和边界条件都覆盖了。每道题做完，建议对照复杂度分析再问自己一遍“为什么时间复杂度是这个”，而不是只看答案对不对。

5.4 我踩过的几个雷（考研期末复习版）

复习数据结构的这段时间，我踩过一些不算罕见但很影响心态的坑，提前告诉你：

第一个坑：把二分查找的 mid 算出来之后，直接用nums[mid]比较，却不检查 mid 是否在有效范围内。其实只要你保证了left <= right，mid 一定在区间内，不需要额外检查。但是如果你的 left 和 right 初始化写反了，那 mid 就可能越界，所以初始化是最值得检查的第一步。

第二个坑：手写 BST 查找时递归出口只写了node == NULL，忘记写node->data == target，导致找到了却在进入下一层时才返回空。这种 bug 特别隐蔽，因为部分测试用例能通过，只有 target 就是根节点时才失败。

第三个坑：归并的测试数组只测了正序，没测逆序。逆序数组能帮你验证循环结束时剩余元素拷贝是否写对。如果只测恰好一个数组先空的情况，另一个数组剩余拷贝的代码永远是死代码，直到某次换数据才爆出来。

第四个坑：把 BST 的中序遍历和查找混在一起理解。中序遍历输出升序序列是 BST 的“验证方法”，但它不是查找方法，查找不需要完整遍历整棵树。如果你用中序来找目标，复杂度就是 O(n) 而不是 O(log n)，那就不是 BST 查找了。

6. 综合实验：用 C 语言把它们组合成一套查找系统

6.1 实验场景设计

如果只是零散地写三个独立函数，总觉得少了点实战感。这里给出一个我当时做数据结构课程设计时的小场景，把三个主题全部串起来：

实验场景：假设你有一个学生成绩管理系统，需要支持三个功能：

1. 两个班级的成绩单（各自按学号升序排列）合并成一个总的成绩单，仍按学号升序。
2. 在合并后的总成绩单中用二分查找快速定位指定学号的成绩。
3. 将学生数据构建成二叉搜索树（按学号为 key），支持按学号查找学生信息。

这个场景最妙的地方在于，三个功能刚好用到三种算法，且数据结构从线性到树形递进，非常贴合“数据结构”这门课从表到树的章节安排。

6.2 关键代码与运行结果示例

功能 1 的有序表归并代码就是第 2 节那段。这里重点说功能 3 的构建和查找组合，因为它是很多人做课程设计时写不对的地方：

// BST 插入节点（构建树时使用） BSTNode* bstInsert(BSTNode* root, int id) { if (root == NULL) { BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode)); newNode->data = id; newNode->left = NULL; newNode->right = NULL; return newNode; } if (id < root->data) { root->left = bstInsert(root->left, id); } else if (id > root->data) { root->right = bstInsert(root->right, id); } // 如果 id 等于 root->data，按题目约定不重复插入，直接返回 return root; }

把合并后的数组合成一个 BST，用循环依次调用bstInsert即可。运行时我会加打印辅助观察：

成绩单合并结果：1001 1003 1005 1008 1012 1017 1020 二分查找学号 1008，找到，成绩为 88 BST 查找学号 1005，找到，成绩为 76 BST 查找学号 2000，未找到

看到这个输出，基本可以确认三个模块都工作正常。

实验里我特意加了“BST 查找不存在的学号”这个用例，因为这是最容易出问题的——很多人只在树的节点上找到了 target，忘记测试查找失败时函数是否正确返回 NULL。

6.3 实验完成后的复盘清单

实验做完后不要急着交，按下边这个清单复盘一遍：

1. 归并函数是否处理了一个数组为空的边界？
2. 二分查找是否用两个不同数据规模的数组测过？
3. BST 是否包含重复数据？重复时你的插入策略是什么？（这里我用的是不重复插入）
4. 三个函数的时间复杂度是否能在汇报时清晰讲出来？
5. 是否测试过“查找不存在元素”的失败分支？

如果这五项全部通过，这个实验基本就是满分水平了。更关键的是，做完这一套，你对有序表归并、二分查找、二叉搜索树查找的理解会比单纯看书深刻得多。

7. 从“会写”到“理解”：我踩过的认知误区

7.1 误区一：认为二分查找就是“取中间比较而已”

这句话没错，但太粗糙。真正常考的边界、死循环、溢出，都是因为没抓住“区间定义”和“循环不变量”。理解二分查找的关键不是会写循环，而是会用区间语言描述整个搜索过程。如果你能用语言讲清楚“为什么 left 要等于 mid + 1 而不是 mid”，那才算真明白了。

我刚开始学的时候就是只背模板，结果遇到“查找第一个大于等于 target”的变种题直接懵掉，后来花了两个小时用画图法把闭区间和左闭右开全部推演一遍，才彻底打通这个障碍。

7.2 误区二：把 BST 的查找效率默认成 O(log n)

很多教材在介绍 BST 时都会写“平均时间复杂度 O(log n)”，但很少强调这是建立在随机插入前提下。如果插入顺序有序，比如插入 1, 2, 3, 4, 5，BST 会变成一条只有右子节点的链，查找 5 要遍历 5 个节点，复杂度 O(n)。

所以你在跟别人讨论 BST 时，一定要说清楚“平均”和“最坏”的区别，否则面试官追问很容易暴露理解深度。当然，这也是红黑树、AVL 树存在的意义。

7.3 误区三：认为树形结构就是高级的，数组就是低级的

数组二分查找在静态数据场景下非常高效：缓存友好、不需要维护指针、常数小。而 BST 因为有指针跳转，在 CPU 缓存层面反而更慢。做工程选型时，数据规模小且静态，直接数组二分可能比红黑树更快。

这个认知误区来自我自己的经历：最初总觉得“树比数组高级”，实际用性能测试打脸后，才意识到数据结构的选择一定要结合访问模式和数据规模。这也是数据结构这门课真正想锻炼的能力。

8. 复习与面试常见问题速查

8.1 分组复习建议

如果时间紧张（比如期末只剩三天），建议这样分配：

• 第 1 天：专门写归并，包括数组版和链表版，写完后做 1-2 道合并有序链表的题。
• 第 2 天：专门写二分查找，把闭区间、左闭右开两种模板各写三遍，整理成自己的速查笔记，然后做查找区间和旋转数组的题。
• 第 3 天：专门写 BST 的查找、插入，把递归和迭代各写一遍，然后用中序遍历验证树是否正确，再做验证 BST 的题。

每天大概 2 小时足够。关键是每天只专注一个知识点，不要三碗饭同时端起来吃。

8.2 面试现场怎么跟面试官沟通

面试手撕二分查找或 BST 时，不要一上来就闷头写。正确节奏是：

1. 先跟面试官确认输入是否有重复元素、数组是否已排序、是否可以修改原数据。
2. 说出你的思路：用闭区间还是左闭右开，几个指针，复杂度和边界怎么处理。
3. 边写边注释，写完主动指出 mid 防溢出这个工程细节。
4. 最后自己说出测试用例和边界条件，比如空数组、只有一个元素、target 比最小值还小等。

这个流程的实际好处是，即使你代码里有一点瑕疵，面试官也已经看到了你的思考过程。我在模拟面试中测试过这个流程，反馈明显优于闷头写题的情况。

8.3 一个小彩蛋：用二分思想求平方根整数部分

最后分享一个把二分查找用到极致的小题：求非负整数 x 的平方根的整数部分，不能用浮点库函数。

思路是在 [0, x] 区间做二分，找到最大的 m，使得 m * m <= x。因为满足条件的是“最后一个满足条件”，所以用 lowerBound 变种的思路：

int mySqrt(int x) { int left = 0, right = x; while (left <= right) { int mid = left + (right - left) / 2; long long square = (long long)mid * mid; // 防溢出 if (square <= x) { left = mid + 1; } else { right = mid - 1; } } return right; // 最后一次满足 square <= x 的位置 }

这道题几乎是二分查找面试题的“内卷之最”，但确实能一次性检验你三个能力：边界控制、防止溢出、返回值语义。如果这道题你能自己推出来并解释清楚返回为什么是 right，那二分查找这部分已经过关了。

我做到这里时还有个习惯——把每道题的思路用自己的话写一遍，不抄书上的话。写出来的文字看着粗糙，但确实是自己消化过的东西。后续再看，特别有成就感，也特别容易发现自己哪个环节其实是模糊的。这个方法推荐给你。