LeetCode Hot 100 里的第 35 题“搜索插入位置”是我见过最容易被低估的二分查找题。它连题目描述都短得不像话给定一个排序数组和一个目标值在数组中找到目标值如果存在就返回它的索引如果不存在则返回它会被按顺序插入的位置。可就是这么一道看起来二十分钟就能搞定的题我在不同场合见过不少候选人翻车有人写对了但是解释不清楚有人用二分却栽在边界条件上还有人甚至连暴力解都写得磕磕绊绊。如果你正准备刷 hot100 题或者正在系统复习算法面试这道题一定值得你停下脚步多看两眼。题目考察的东西非常聚焦你知不知道在有序数组里可以用二分查找把时间复杂度压到 O(log n)你能不能把“找插入位置”翻译成“找第一个不小于目标值的下标”。很多 Hot 100 的经典题本质上都是在反复用这个小小的基础能力。所以别嫌它简单把这一题吃透后面做“在排序数组中查找元素的第一个和最后一个位置”“搜索旋转排序数组”都会顺手很多。1. 搜索插入位置到底在问什么先别急着写码1.1 题目规则与三种命中情况题目给一个升序排列的整数数组nums和一个目标值target让你返回目标值在数组中的索引如果目标值不存在就返回它按顺序插入后应该占的位置。题目一句话但里面藏着四种完全不同的情况目标值就在数组中间目标值小于数组第一个元素目标值大于数组最后一个元素以及目标值不在数组但落在某两个元素之间。举个经典例子nums [1, 3, 5, 6]。如果target 5答案显然是 2因为 5 就在数组里。如果target 2数组里没有 2但它应该排在 1 和 3 之间也就是下标 1 的位置。如果target 7它比 6 还大应该追加到数组末尾答案就是数组长度 4。如果target 0它比 1 还小应该插到最前面答案是 0。这四种情况凑在一起才是题目的全貌。很多人刷这题时只测了“目标值存在”和“落在中间”这两种情况偏偏漏了“比所有数都小”和“比所有数都大”这两个边界。结果代码在力扣上一跑就报错然后开始怀疑二分模板。其实不是模板的问题是你对题意的理解不够完整。你可以把返回结果理解成在数组里找到第一个 target的元素位置如果所有元素都小于target就返回数组长度。这样一转换所有情况都能统一处理。1.2 为什么一个“简单题”能进 Hot 100Hot 100 是很多人刷题的主线里面的题不一定都难但一定都是面试里出现频率高、又能承载核心知识点的题。“搜索插入位置”能进 Hot 100核心原因是它把二分查找最本质的东西讲清楚了你不需要在数组里精确找到一个值而是找到一个满足条件的分界点。这个分界点就是“第一个不小于 target 的位置”。很多人在学二分时只记住了一个模板却不理解每个变量为什么这么移动。这题恰好逼你去思考当nums[mid] target时说明mid以及它左边所有元素都太小答案只能在右边当nums[mid] target时说明mid有可能是答案但左边可能还有更靠前的答案。这个思考过程就是二分查找的灵魂。另外这题也是C里lower_bound和Python里bisect_left的底层逻辑。你如果以后做工程要在有序数组里找插入点本质上就是在实现这个函数。所以它虽然标着“简单”却是很多中等难度题的地基。把这道题理解到位你在二分查找专题里就算真正入门了。2. 从暴力到二分先写出能跑的代码再说2.1 线性扫描最直观但不够用的解法如果我们不考虑时间复杂度这题的暴力解法非常直接从左到右遍历数组找到第一个大于等于target的元素就返回它的下标如果遍历完都没找到就返回数组长度。写成代码更短def searchInsert(nums, target): for i, num in enumerate(nums): if num target: return i return len(nums)这段代码能通过力扣的大部分测试用例因为数组无序时你只能这么做。但题目明确要求时间复杂度是 O(log n)因为数组是有序的你有更好的选择。线性扫描的时间复杂度是 O(n)在数据量大的时候会慢很多而且面试官看到你遍历有序数组大概率会追问一句“能不能更快”不过我不建议你完全跳过暴力解。实际面试中先给出一个正确但不高效的解法再说“因为数组有序我们可以用二分把复杂度降到 O(log n)”这是一个很加分的沟通顺序。它说明你不是在背题而是真的在根据题目条件做优化。暴力解还可以用来验证二分解法的正确性本地写一个测试函数随机生成数组和 target比较两个函数的输出能帮你快速发现边界条件写没写对。2.2 暴力解在面试中的信号价值很多刷题的人只追求“一上来就写出最优解”觉得写暴力解很丢人。我在面试别人时反而觉得遇到一个问题能快速给出可行方案比死磕最优解更重要。尤其像这种简单题你先给出 O(n) 的解法等于告诉面试官我理解问题我也知道 baseline 是什么。然后再提出二分等于告诉面试官我还能根据题目特性做优化。但这里有个前提你不能只停留在暴力解。如果你说“数组有序所以我们可以用二分”然后写不出来那面试印象分会掉得很厉害。更好的策略是在你脑海里的执行顺序永远是先确认题意再想暴力做法再思考能不能用有序性、二分、双指针等技巧优化。这套思路不仅适用于这一题也适用于绝大多数算法题。我自己刷题时会专门把暴力解和最优解都写在本地笔记里。暴力解不是没有价值它是一个天然的“测试基准”。后面你写二分写得很自信但跑测试用例挂了你可能会怀疑是边界处理问题这时候用暴力解一对比马上就能定位是哪里出了偏差。所以别急着删掉暴力代码把它留在本地当对照工具省心很多。3. 二分查找的完整推导手把手拆给你看3.1 闭区间写法左右指针与循环条件二分查找的写法有很多种我先讲最常用的闭区间写法。左右指针分别指向数组的第一个和最后一个元素也就是left 0right len(nums) - 1。循环继续进行时搜索区间是[left, right]所以用while left right。每次取中间位置mid然后比较nums[mid]和target来决定往哪边收缩。先看完整代码def searchInsert(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return left这里我先解释mid的计算。很多人习惯写(left right) // 2这在大多数语言里没问题但万一left和right都接近上限相加可能溢出。写成left (right - left) // 2能彻底避免这个问题面试时这个小细节也会被看作你有工程意识。然后是判断条件。当nums[mid] target时说明mid以及它左边的所有元素都小于目标值答案不可能是这些位置所以把左边界移到mid 1。当nums[mid] target时说明mid有可能是答案但左边可能还有更靠前的位置所以把右边界移到mid - 1。循环结束之后left所在的位置就是答案。如果你用 C 写思路完全一样只是类型上要注意class Solution { public: int searchInsert(vectorint nums, int target) { int left 0; int right (int)nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; } };注意 C 里我特意把nums.size()转成了int。因为size()返回的是无符号整数如果数组为空nums.size() - 1会变成一个巨大的正数导致left right判断出问题。这是新手最容易踩的坑后面我会再详细说。3.2 为什么最后返回 left 而不是 mid 或 right这是全题最关键的地方。很多人把代码背下来了知道返回left但被面试官一问“为什么不是mid”就卡住。要理解这个问题得看二分过程中隐含的不变量。在闭区间写法里left左边的所有元素都严格小于targetright右边的所有元素都大于等于target。你可以把left看成“答案的下界”把right看成“答案的上界”。循环每执行一次这个不变量都不会被破坏如果nums[mid] target说明mid可以归入“左边小于 target”的区域所以left移到mid 1如果nums[mid] target说明mid可以归入“右边大于等于 target”的区域所以right移到mid - 1。循环结束的条件是left right。此时区间为空但left依然满足left左边都小于 targetleft自身以及右边都大于等于 target。所以left就是第一个 target的位置。mid在最后一次执行后可能等于left也可能等于right它不是我们需要的稳定信息。right则是left - 1它右边才满足条件如果返回right在目标值不存在时就会指到最后一个比target小的元素上答案错得离谱。我建议你拿nums [1, 3, 5, 6]、target 2手动模拟一遍。初始left 0、right 3中间位置是 1nums[1] 3 2所以right变成 0。接着left 0、right 0中间位置是 0nums[0] 1 2所以left变成 1。此时left right循环结束返回1正好是 2 应该插入的位置。手动模拟一次之后“为什么返回 left”就再也忘不掉了。3.3 开区间写法另一种常见模板除了闭区间写法还有一种开区间写法也很常见它就是标准库lower_bound的实现思路。区别在于初始right len(nums)搜索区间是[left, right)循环条件是while left right。def searchInsert(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left开区间写法的好处是语义很清晰left和right分别表示“答案可能存在的左边界和右边界”且right本身不包含在搜索区间内。所以当nums[mid] target时mid不可能是答案left可以直接跳到mid 1当nums[mid] target时mid有可能是答案就不能把right减一跳过它只能把right收缩到mid。循环结束时left right这个位置就是答案。两种写法都能 AC没有绝对的对错。但我个人更推荐你先吃透闭区间写法因为它更容易从“维护不变量”的角度去推理left永远指向第一个 target 的位置right永远指向最后一个小于 target 的位置。想清楚这一点再切换到开区间写法就很快了。如果你感觉闭区间写法容易搞混和那可以试试开区间很多人觉得它更符合直觉。4. 边界条件与常见坑自己踩过的都写在这里4.1 直接穿到数组末尾的案例边界条件永远比主流程更容易出错。拿target 7来模拟闭区间代码nums [1, 3, 5, 6]初始left 0、right 3中间位置是 1nums[1] 3 7所以left变成 2接着left 2、right 3中间位置是 2nums[2] 5 7left变成 3再接着left 3、right 3中间位置是 3nums[3] 6 7left变成 4。此时循环结束返回 4正好是数组长度。这个案例看起来简单但最容易出错的地方是如果返回right你会得到 3也就是“最后一个小于 target 的元素的位置”而不是插入位置。如果返回mid在最后一次循环里mid 3你也会得到 3同样是错的。只有left在我们这个二分结构下才会变成n。所以写完代码后一定要在脑子里或者草稿纸上把“目标值大于所有元素”这条路径完整跑一遍。我还见过有人在返回前加一句特判比如在开头判断target nums[-1]直接返回len(nums)。这不是不行但属于画蛇添足。二分代码本身天然能处理这个边界额外特判反而增加了代码分支面试时还容易漏掉其他情况。保持主干干净用不变量解释结果才是正解。4.2 空数组和单元素数组空数组是很多二分写法翻车的重灾区。在 Python 里len(nums) - 1得到-1while left right不会执行直接返回left 0正确。但在 C 里如果写成int right nums.size() - 1;因为nums.size()是size_t无符号类型空数组时nums.size() - 1是一个很大的正数循环会进入访问nums[mid]直接越界。所以 C 一定要转成int或者先做空数组判断。单元素数组也需要验证。假设nums [2]target 1闭区间初始left 0、right 0mid 0nums[0] 2 1所以right -1循环结束返回 0正确。如果target 2nums[0] 2 2为假走else分支right -1返回 0也正确。如果target 3nums[0] 2 3left 1返回 1也正确。这个单元素用例可以帮你同时验证等于、小于、大于三种情况。空数组和单元素数组在力扣测试用例里几乎必现所以不是“概率问题”而是“一定要提前处理”的问题。我的习惯是写完二分后先手动跑这几个输入空数组、长度为 1 的数组、target小于第一个元素、target等于中间某个元素、target大于最后一个元素。全跑通了再提交代码基本一次过。4.3 关于重复元素的疑问题目说“排序数组”没说“没有重复元素”。当数组里有重复元素时插入位置应该怎么算比如nums [1, 3, 3, 5]target 3。你可能会想返回 1 还是 2 都可以其实按照题意目标值存在时返回它的索引但如果有多个相同值并没有明确说返回哪个。在力扣 35 的测试用例里通常返回任意一个存在的位置都能通过但使用二分处理的普遍结果是返回第一个等于 target 的位置。原因在于我们的二分条件当nums[mid] target时会走else分支不断把right往左压。也就是说即使nums[mid] target我们也认为“答案可能在更左边”于是继续向左搜索。最终left会停在第一个等于 target 的位置。如果你想返回最后一个等于 target 的位置那就得改变策略在nums[mid] target时往右压这对应的是upper_bound的语义。很多人在做后续题“在排序数组中查找元素的第一个和最后一个位置”时会突然觉得二分很难。其实根源就在这里你没有区分lower_bound和upper_bound。如果把 35 题理解成“在数组中找 lower_bound”那么后面的变体题就只是小改动。趁着做 35 题把重复元素的情况想清楚对后面帮助巨大。5. 从 35 题看二分查找的套路化扩展5.1 通用 lower_bound 模板从 35 题抽象出来的模板本质上是一个“通用查找函数”在一个升序数组里找到第一个满足某种条件的元素位置。这个条件可以是“大于等于 target”“大于 target”也可以是“小于等于 target 的最后一个位置”等等。关键点在于你要清楚当条件成立时是把区间往左压还是往右压。下面这个闭区间模板可以覆盖大部分二分查找问题def binary_search_condition(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if 条件不成立: left mid 1 else: right mid - 1 return left不同的题只改“条件不成立”这一行、以及最后的返回值。比如要找第一个 target的位置条件就是nums[mid] target时不成立于是左移要找第一个 target的位置条件就成了nums[mid] target时不成立。你不需要背多个模板只要记住一句话我们找的是一个分界线左边的元素不满足最终条件右边的元素满足最终条件left最终会停在分界线上。这个模板对我来说最大的价值是统一了记忆成本。以前我看到各种二分写法什么left right、right mid、right mid - 1非常容易记混。后来我把所有问题都往“条件不成立就 left 右移”这个框架里套每次只需要仔细定义“条件”是什么代码反而很少写错。35 题就是练这个框架最好的起点。5.2 三个高频变体上界、下界、插入点利用 35 题的思考方式可以快速推导出几个高频变体。第一个是找第一个大于等于 target 的位置也就是lower_bound这是 35 题本身。第二个是找第一个大于 target 的位置也就是upper_bound。第三个是找最后一个小于 target 的位置它其实就是lower_bound(target) - 1。我在下方用一个表格把这些变体整理出来方便你对照需求二分条件返回值对应语义第一个大于等于 targetnums[mid] target时左移leftlower_bound35 题第一个大于 targetnums[mid] target时左移leftupper_bound最后一个小于 target先求第一个大于等于 target再减一left - 1没有 target 时插入前一个位置最后一个小于等于 target先求第一个大于 target再减一left - 1类似upper_bound前一位为什么要单独记这些因为在真实面试里题目不会永远直白地说“找插入位置”。它可能说“寻找峰值”“寻找旋转排序数组中的最小值”“搜索二维矩阵”这些题本质上都是在有序空间里找“分界线”。你如果能在 35 题阶段就把“第一个满足条件的位置”这个思维练熟后面面试遇到变体时你就不是在背题而是在用同一个底层模型解决问题。我自己的经验是不要一次性把变体全背完而是做 35 题时只理解lower_bound然后找“在排序数组中查找元素的第一个和最后一个位置”这题来练upper_bound。一道题对应一个变体用题目本身来巩固比单独背表格更牢靠。5.3 面试中怎样把套路讲出亮点面试官见过太多背模板的候选人。如果你一上来就说“这题用二分”然后默写代码即使写对了可能也只是“合格”不够“亮眼”。但如果你能说出“我们要找的是第一个不小于 target 的位置所以二分过程中维护的其实是一个分界线”面试官会觉得你真的理解了。我建议你按这个节奏讲先解释题意把目标值存在和不存在的情况都列出来然后说“数组有序所以二分查找可以把复杂度降到 O(log n)”接着在白板上画一下分界线说明left左侧都小于 targetleft右侧都大于等于 target最后写代码并用一个边界用例手动验证。整个过程不需要背稿重点是把你脑中“为什么返回 left”的推理过程展示出来。还有一个小技巧写完代码后主动说“我再用空数组和 target 大于所有元素这两个例子验证一下边界”。这句话会让面试官觉得你很稳因为很多候选人写完就交根本不做自测。这不仅是 35 题的方法也是所有算法题的通用加分项。6. 这道题带给我的刷题建议与面试心得6.1 刷 Hot 100 的正确顺序Hot 100 是很多人面试前的主线题库但我不建议你从头到尾按编号刷。比较有效的做法是先按专题分组比如数组、链表、二叉树、动态规划、二分查找每一个专题内部由易到难推进。“搜索插入位置”在二分专题里就非常适合放在靠前的位置它比 704 二分查找多了一层“插入位置”的思考又比 34 题和 33 题简单很多。我刷 hot100 题时会做一件小事每道题在题解开头写一句“本质”。比如 35 题的本质是“在升序数组中找 lower_bound”。这句话听起来简单但等刷到 34 题看到“第一个和最后一个位置”你就能立刻反应出这是 lower_bound 和 upper_bound 的组合。如果没有 35 题打底34 题容易让人绕晕。所以我对这题的态度是别因为它简单就跳过。在 Hot 100 里简单题往往是用来建立“概念锚点”的。你后面刷到任何二分变体都可以回来看看这题重新确认一下“返回 left 的原因”和“不变量”到底是怎么一回事。这个概念锚点越牢固后面越不容易乱。6.2 现场写这题的节奏与沟通技巧如果你在面试里遇到这题节奏可以这样把握第一步确认输入。问清楚是否升序、是否可能有重复元素、目标值是否一定在数组范围内。虽然力扣题目都会写清楚但现场沟通中主动确认会让面试官觉得你严谨。第二步说思路。你可以说“我打算先用线性扫描给出一个 O(n) 的 baseline再基于数组有序性优化到 O(log n) 的二分查找”。这个顺序既展示了你理解问题也展示了你优化能力。第三步写代码。闭区间写法比较稳定我在面试中一般用这个。代码行数不多但你要边写边解释边界更新为什么left mid 1为什么right mid - 1为什么最后返回left。写完之后不要急着说“完成了”而是拿一个例子手动跑一遍比如nums [1, 3, 5, 6]、target 2你可以在白板上写下left、right、mid的变化过程让面试官看到你的自测能力。我见过不少候选人代码写对了但对“为什么返回 left”支支吾吾。这种情况很可惜因为面试官本来要从这一题看出你对二分查找的理解深度。只要你能把不变量讲清楚哪怕中间代码有点小问题面试官通常也会愿意引导你修正反而容易拿到更好的评价。6.3 最后的一点体会这题我至少刷过四遍每次重刷都有新的体会。第一次我只是在背模板能 AC 但没想明白第二次我手动模拟了target大于所有元素的情况突然理解了left为什么会走到数组末尾第三次我在做 34 题时发现原来这题就是lower_bound而 34 题需要lower_bound和upper_bound两个函数组合第四次我开始尝试用开区间写法发现两种模板其实殊途同归。如果你现在正准备刷 Hot 100别急着把 35 题划掉。花一点时间把边界条件想明白哪怕只是多看几眼“为什么返回 left”这个点都会在后面的二分题里给你回报。这题不长但它教给你的思考方式能陪你走很远。