有序表归并、二分查找与二叉搜索树查找：原理、边界条件与实战对比

开头写这篇笔记之前我其实已经把这一part的内容反复看了三遍。原因很简单有序表归并、二分查找、二叉搜索树查找这三个主题表面上看是三个独立的知识点实际在数据结构的学习里是同一根藤上结出来的瓜——它们都在解决“怎么在一片数据里快速找到目标”区别只是数据组织方式不同、查找策略不同。尤其是对考研党、期末复习党和刚转行刷算法的人这三个点几乎每次考试和面试都会被拎出来单考但很少有人告诉你它们内部的联系和边界条件为什么要这么抠。这篇文章就把这三个东西放在一起做一个整合笔记包含核心思路、可复现代码、复杂度分析、常见坑点以及我实际刷题和复习时踩过的雷。适合正在学《数据结构》这门课的学生、准备面试的开发者以及想系统过一遍查找算法的朋友。看完你应该能达到这样一个效果给你一道题你能快速判断该用有序表归并、二分查找还是二叉搜索树并且边界条件不再靠猜。1. 为什么把这三个主题放在一起学1.1 三个主题的关联点都建立在“有序”之上先理清逻辑。有序表归并解决的是“把两个已经有序的序列合成一个依然有序的序列”二分查找解决的是“在一个已经有序的序列里快速定位目标值”而二叉搜索树查找解决的是“在一棵满足左小右大的树结构里快速定位目标值”。你看三者的前提条件全部指向同一个词——有序。这个关联不是巧合。很多初学者会以为二叉搜索树和二分查找是两套完全独立的东西实际上二叉搜索树的查找过程本质上就是在执行一种“二叉化”的二分查找每次比较后丢弃一半子树跟二分查找每次比较后丢弃一半区间是同一个逻辑。区别在于二分查找的底层是连续存储数组支持随机访问所以可以直接用下标算中点二叉搜索树的底层是链式存储节点和指针没有随机访问能力所以用树的分支结构来模拟“丢弃一半”的过程。我在复习的时候把三个主题串成一条线效果比分开记好得多。推荐你也这样学。1.2 学习路径怎么安排最省力建议顺序是有序表归并 → 二分查找 → 二叉搜索树查找。理由有两点。第一归并是最直观的入门。它只涉及线性扫描和指针移动不需要复杂的递归思维也不需要理解循环不变量。把归并写顺了你对“指针/下标移动控制循环”这件事就有了手感这个手感是二分查找和二叉树遍历共用的基础能力。第二二分查找可以作为“数组版查找”的收官二叉搜索树作为“链表版查找”的进阶。二分查找的难点在于区间定义和边界更新二叉搜索树的难点在于递归理解和树形结构的状态维护。一个偏重“循环细节”一个偏重“递归结构”用这个顺序学思维难度是逐步抬升的不会一上来就被递归整懵。注意不要一上来就试图背代码模板。边界条件这种东西背得快忘得也快必须理解区间定义之后自己推导一遍才能应变各种变种题。2. 有序表归并最容易被忽视的基础功2.1 归并的核心思想与适用场景有序表归并简单说就是有两个已经各自排好序的线性表通常是数组把它们合并成一个整体有序的线性表。经典的归并排序中Merge 操作就是干这件事的所以它也是归并排序的核心子过程。为什么说它容易被忽视因为很多教材把这部分放在“线性表”章节里一笔带过学生也觉得“不就是把两个数组接起来再排序吗”。我刚开始也有这个想法直到做数据结构实验时才明白这个操作的关键约束是要求时间复杂度 O(mn)不能直接用排序算法重排。也就是说你必须利用两个输入序列本身有序这个条件用线性扫描完成合并。适用场景非常广归并排序、多路归并外部排序、合并两个有序链表、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的空间必须由调用方事先分配足够大至少 mn函数内部不能假设数组够大否则写越界就是经典的内存错误。这在 C 语言里尤其关键C 用 vector 可以规避一部分风险但底层逻辑完全一样。另一个细节是和的选择。用可以保证当两个元素相等时优先取前一个数组的元素这是归并排序稳定性的来源。如果改成两个数组的相等元素顺序会交换导致归并排序不稳定。在做不需要稳定性的场景下两种写法都对但如果你在实现归并排序并且要求稳定必须写成。链表版的有序表归并逻辑上完全一致只是把数组下标换成指针移动递归写法里常见的“虚拟头节点”技巧可以省去大量空指针判断建议实习时优先用虚拟头节点。2.3 归并的复杂度、边界条件与易错点时间复杂度是 O(mn)因为两个数组各被扫描一次空间复杂度是 O(mn)因为需要额外的结果数组。如果是链表版原地合并空间复杂度可以做到 O(1)。实际写代码最容易翻车的三个地方循环结束后的剩余元素处理写漏。两个主循环结束后必定有一个数组还剩元素两个 while 拷贝语句必须都写上。有些人只写一个测试用例恰好第一个数组先空就过了换一组数据立刻崩。结果数组的下标 k 自增顺序写错。mergeArr[k] arr1[i]这句话里 k 的自增必须放在赋值之后写成mergeArr[k] arr1[i]; k; i;等价但不要写成mergeArr[k]否则第一个元素会写到下标 1下标 0 变成未初始化的脏数据。输入数组本身不是有序的。有序表归并的前提是两个输入有序如果调用方传入无序数组结果必然错误。严谨的做法是在函数注释里明确前置条件或者在测试前用断言检查。我自己的习惯是写完归并函数后先用三个用例自测——两个等长数组、一个数组为空、两个数组长度悬殊。这三个用例跑通基本能覆盖所有边界。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]要么是[mid1, right]。如果你定义搜索区间是左闭右开[left, right)那么right指向的元素已经被排除在外循环条件是while (left right)更新时right mid因为 mid 已经被检查过且右边界是开区间所以可以直接取 midleft 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你可以轻松实现第一个等于 targetidx lowerBound(nums, size, target)检查nums[idx] target即可。第一个大于 targetlowerBound(nums, size, target 1)。最后一个等于 targetlowerBound(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 TreeBST是这么一棵二叉树对于任意节点它的左子树中所有节点的值都小于该节点的值右子树中所有节点的值都大于该节点的值且左右子树本身也都是二叉搜索树。这个定义非常简洁但你要仔细把它跟普通二叉树区分开。普通二叉树对节点值没有任何要求所以查找只能遍历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 树结构已构建底层存储数组或链表数组连续链式节点平均时间复杂度O(mn)O(log n)O(log n)平衡时最坏时间复杂度O(mn)O(log n)O(n)退化成链额外空间复杂度O(mn)数组/ O(1)链表O(1)迭代O(1)迭代/ O(log n)递归栈典型应用归并排序、合并有序链表查找数字、求平方根、旋转数组动态集合查找、数据库索引思想是否适合动态数据否否是这张表的结论非常直接静态数据且需要快速查询优先二分查找动态数据且频繁插入删除优先 BST或平衡树处理多个有序序列优先归并思路。5.2 典型题型的破题思路以我刷题的经验这三个主题常见的题型大概有这么几类每类给出破题点。第一类合并两个有序数组/链表。这道题几乎就是有序表归并的原题破题点是“谁小谁先走”注意链表版用虚拟头节点处理空指针。变种题“合并 K 个有序链表”则要用优先队列堆但这已经是高级版本了初学阶段不用强求。第二类在有序数组或旋转有序数组中查找目标值。这是二分查找的经典应用。常规数组直接二分旋转数组需要额外判断哪半部分是有序的核心是先跟nums[left]比较确定 mid 落在哪个有序区间再判断 target 在不在这个区间里。第三类验证一棵树是不是 BST、在 BST 中查找最近公共祖先。验证 BST 用中序遍历看是否递增或递归时给每个节点传一个上下界区间。查找 LCA 则利用 BST 特性——如果两个节点都在当前节点左侧去左子树找都在右侧去右子树找否则当前节点就是 LCA。第四类BST 中查找第 k 小的元素。解法是 BST 的中序遍历是升序序列用中序遍历计数到第 k 个即可。更高效的树形结构是给每个节点维护子树节点数这个属于进阶考试很少单独考。5.3 一套自测题目清单附难度标记在这里收集了 9 道自测题按难度分三档适合学完这章后进行自我检验。题目尽量选经典、常见、可验证的入门档适合刚学完基础合并两个有序数组到第三个数组要求 O(mn)。难度低。给定有序数组和目标值返回目标值的下标不存在返回 -1。难度低。给定一棵二叉树判断它是否是合法的二叉搜索树。难度中低。进阶档适合复习与面试准备 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 rightmid 一定在区间内不需要额外检查。但是如果你的 left 和 right 初始化写反了那 mid 就可能越界所以初始化是最值得检查的第一步。第二个坑手写 BST 查找时递归出口只写了node NULL忘记写node-data target导致找到了却在进入下一层时才返回空。这种 bug 特别隐蔽因为部分测试用例能通过只有 target 就是根节点时才失败。第三个坑归并的测试数组只测了正序没测逆序。逆序数组能帮你验证循环结束时剩余元素拷贝是否写对。如果只测恰好一个数组先空的情况另一个数组剩余拷贝的代码永远是死代码直到某次换数据才爆出来。第四个坑把 BST 的中序遍历和查找混在一起理解。中序遍历输出升序序列是 BST 的“验证方法”但它不是查找方法查找不需要完整遍历整棵树。如果你用中序来找目标复杂度就是 O(n) 而不是 O(log n)那就不是 BST 查找了。6. 综合实验用 C 语言把它们组合成一套查找系统6.1 实验场景设计如果只是零散地写三个独立函数总觉得少了点实战感。这里给出一个我当时做数据结构课程设计时的小场景把三个主题全部串起来实验场景假设你有一个学生成绩管理系统需要支持三个功能两个班级的成绩单各自按学号升序排列合并成一个总的成绩单仍按学号升序。在合并后的总成绩单中用二分查找快速定位指定学号的成绩。将学生数据构建成二叉搜索树按学号为 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 实验完成后的复盘清单实验做完后不要急着交按下边这个清单复盘一遍归并函数是否处理了一个数组为空的边界二分查找是否用两个不同数据规模的数组测过BST 是否包含重复数据重复时你的插入策略是什么这里我用的是不重复插入三个函数的时间复杂度是否能在汇报时清晰讲出来是否测试过“查找不存在元素”的失败分支如果这五项全部通过这个实验基本就是满分水平了。更关键的是做完这一套你对有序表归并、二分查找、二叉搜索树查找的理解会比单纯看书深刻得多。7. 从“会写”到“理解”我踩过的认知误区7.1 误区一认为二分查找就是“取中间比较而已”这句话没错但太粗糙。真正常考的边界、死循环、溢出都是因为没抓住“区间定义”和“循环不变量”。理解二分查找的关键不是会写循环而是会用区间语言描述整个搜索过程。如果你能用语言讲清楚“为什么 left 要等于 mid 1 而不是 mid”那才算真明白了。我刚开始学的时候就是只背模板结果遇到“查找第一个大于等于 target”的变种题直接懵掉后来花了两个小时用画图法把闭区间和左闭右开全部推演一遍才彻底打通这个障碍。7.2 误区二把 BST 的查找效率默认成 O(log n)很多教材在介绍 BST 时都会写“平均时间复杂度 O(log n)”但很少强调这是建立在随机插入前提下。如果插入顺序有序比如插入 1, 2, 3, 4, 5BST 会变成一条只有右子节点的链查找 5 要遍历 5 个节点复杂度 O(n)。所以你在跟别人讨论 BST 时一定要说清楚“平均”和“最坏”的区别否则面试官追问很容易暴露理解深度。当然这也是红黑树、AVL 树存在的意义。7.3 误区三认为树形结构就是高级的数组就是低级的数组二分查找在静态数据场景下非常高效缓存友好、不需要维护指针、常数小。而 BST 因为有指针跳转在 CPU 缓存层面反而更慢。做工程选型时数据规模小且静态直接数组二分可能比红黑树更快。这个认知误区来自我自己的经历最初总觉得“树比数组高级”实际用性能测试打脸后才意识到数据结构的选择一定要结合访问模式和数据规模。这也是数据结构这门课真正想锻炼的能力。8. 复习与面试常见问题速查8.1 分组复习建议如果时间紧张比如期末只剩三天建议这样分配第 1 天专门写归并包括数组版和链表版写完后做 1-2 道合并有序链表的题。第 2 天专门写二分查找把闭区间、左闭右开两种模板各写三遍整理成自己的速查笔记然后做查找区间和旋转数组的题。第 3 天专门写 BST 的查找、插入把递归和迭代各写一遍然后用中序遍历验证树是否正确再做验证 BST 的题。每天大概 2 小时足够。关键是每天只专注一个知识点不要三碗饭同时端起来吃。8.2 面试现场怎么跟面试官沟通面试手撕二分查找或 BST 时不要一上来就闷头写。正确节奏是先跟面试官确认输入是否有重复元素、数组是否已排序、是否可以修改原数据。说出你的思路用闭区间还是左闭右开几个指针复杂度和边界怎么处理。边写边注释写完主动指出 mid 防溢出这个工程细节。最后自己说出测试用例和边界条件比如空数组、只有一个元素、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那二分查找这部分已经过关了。我做到这里时还有个习惯——把每道题的思路用自己的话写一遍不抄书上的话。写出来的文字看着粗糙但确实是自己消化过的东西。后续再看特别有成就感也特别容易发现自己哪个环节其实是模糊的。这个方法推荐给你。