这道题我在LeetCode热题100里刷到的时候第一反应是“这也太简单了吧”结果越写越发现搜索插入位置其实是二分查找里最容易被低估的一道题。它表面上只要求你找到一个插入下标实际上考察的是你对“二分查找终止状态”的理解是面试官最爱拿来试探你边界功底的那类题目。先说清楚这道题是什么给定一个排序数组和一个目标值如果在数组里找到了目标值返回它的下标如果没找到返回它按顺序应该被插入的位置。LeetCode原题编号是35在热门100题单里通常被排在第63位所以标题里写成“63搜索插入位置”。它属于典型的二分查找入门题但也是一堆二分变题的母题从“爱吃香蕉的狒狒”到各种“最大化最小值”问题根子都在这道题的理解上。适合两类人看一类是刚接触二分、被各种边界搞晕的新手另一类是刷了几十道二分题但总在写right mid还是right mid - 1之间犹豫的同学。1. 把题目拆开看它真正考的是什么1.1 题目描述与本质重构原题给了一个升序排列的整数数组nums和一个目标值target要求返回target在数组中的索引如果不存在就返回它会被按顺序插入的位置。运行时间复杂度要求O(log n)。举个例子nums [1,3,5,6]target 5时返回2target 2时返回1因为2应该插在下标1的位置target 7时返回4因为7比所有元素都大要插在末尾。很多新手盯着“插入位置”这四个字会下意识想“我得先判断target在不在数组里不在的话再找插哪”。这是线性思维。实际上你可以把整个问题统一成一个更简洁的表述在数组nums中找到第一个大于等于target的元素下标如果所有元素都小于target则返回数组长度。这句话一出来问题就变味了——它不再是“查找条件判断”两件事而是一个纯粹的“边界位置查找”问题。而“查找第一个满足条件的位置”正是二分查找最擅长的场景。1.2 为什么线性查找不行如果你用暴力解法从数组头开始遍历找到第一个大于等于target的位置就停最坏情况下要遍历整个数组时间复杂度O(n)。而数组是有序的这个前提条件意味着我们可以利用“跳过一半”的策略。二分查找的时间复杂度是O(log n)。假设数组长度是100万线性查找最坏要比较100万次二分查找只需要20次左右。这差距在单次查询上可能感觉不出来但如果查询很多次或者在系统里处理海量数据O(log n)就是唯一能扛住的选择。从面试角度来说题目已经明确写了“时间复杂度O(log n)”或者面试官口头要求那基本就是直接暗示二分。如果题目没写这个要求看到“排序数组”这个关键词第一反应也应该是二分。1.3 从这道题延伸出的经典变体搜索插入位置本身不复杂但它是各种二分变题的地基。我随便列几个相关的在排序数组中查找元素的第一个和最后一个位置LeetCode 34求平方根LeetCode 69用二分逼近整数平方根爱吃香蕉的狒狒LeetCode 875对速度值做二分分割数组的最大值LeetCode 410典型的最大化最小值这些题目里LeetCode 34直接就是“找左边界找右边界”本质就是搜索插入位置的升级版LeetCode 875需要对“速度”这个连续值域做二分和搜索插入位置在“找边界”这个思维上一脉相承。所以你别看这道题写起来就十几行代码把它彻底吃透后面一大片二分题都会轻松很多。2. 二分查找的核心原理与区间模板2.1 二分的本质让候选区间每轮减半讲二分之前总有人问我“二分到底难在哪”。我觉得难在两点一是边界条件二是区间定义。很多人写二分靠背代码边界一换就懵。这里先讲本质。二分查找的思路是在一个有序区间里维护一个“可能包含答案”的范围每轮取中间位置的值根据这个值和目标值的关系把范围缩小一半。关键在于你选的那个“中间值”到底落在区间内的哪个位置以及区间在什么情况下变成空集或者收敛到一个位置。不用把它想得高端。你猜一个1到100之间的数字别人只告诉你“大了”还是“小了”你用二分策略最多7次就能猜中。这个过程中你每次猜的数就是mid剩下的范围就是候选区间。搜索插入位置也一样只是“找某个值”变成了“找第一个不小于target的位置”。2.2 模板一左闭右闭区间先看最常见的模板也就是许多人背过的左闭右闭写法int searchInsert(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }在这个模板里区间[left, right]始终保持“两端都包含”的定义。因为左右都是闭区间所以当mid不是答案时必须将区间收缩到mid1或mid-1否则下一次循环又会把mid包含进去造成死循环。循环结束的条件是left right也就是区间变成空集。这时候left指向的位置就是target应该插入的位置。原理是最后一次出现nums[mid] target时left移到了mid1而所有比target小的元素都在left左边最后一次出现nums[mid] target时right移到了mid-1所有比target大的元素都在right右边。最终left就是“第一个不小于target的下标”。2.3 模板二左闭右开区间我实际写题更常用的是另一个模板左闭右开int searchInsert(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }这个模板有几个鲜明的特点right初始化为nums.size()不包含在候选区间里所以模拟的是区间[left, right)循环条件是left right因为区间永远非空就没有必要等到left rightnums[mid] target时mid肯定不是答案继续找右边left mid 1nums[mid] target时mid可能是答案也可能答案在更左边所以right mid不能跳过mid循环结束时left right这个位置就是要找的边界。很多人一开始不太适应这种写法觉得“怎么没有equal分支”。这个模板的核心思路是不管target存不存在找的都是“第一个大于等于target的位置”。没有显式的相等判断因为“等于”也属于“大于等于”的一部分只需要把等于的情况和大于的情况一起归入right mid。2.4 两个模板怎么选核心判断标准就是你要找的是“精确等于某个值”还是“第一个满足某条件的位置”。如果只是找target是否存在两个模板都行但左闭右闭写法更直观因为相等直接返回。如果找的是边界、插入点、左边界、右边界这类问题左闭右开写法更不容易写错因为它天然保持“left永远指向可行区间左侧右边界”的不变量。我个人的偏好是涉及“找边界”的题目一律用左闭右开模板涉及“精确查值”的题目用左闭右闭模板。搜索插入位置属于“找边界”用左闭右开模板最顺手。3. 代码实现与完整调试记录3.1 C实现与逐行注释用C写左闭右开模板的完整代码class Solution { public: int searchInsert(vectorint nums, int target) { int left 0; int right nums.size(); // 左闭右开区间 [left, right) while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { // mid 位置的元素小于 target说明插入位置在 mid 右侧 left mid 1; } else { // mid 位置的元素大于等于 target说明插入位置可能是 mid 或更靠左 right mid; } } return left; // 循环结束时 left right就是插入位置 } };第8行用left (right - left) / 2而不是(left right) / 2是为了防止leftright溢出。第13行是二分的精髓遇到nums[mid] target就把左边界收缩到mid1因为mid位置的值太小不可能是插入点遇到nums[mid] target就把右边界收缩到mid因为mid本身有可能就是答案不能排除。这个模板在LeetCode 35上可以直接提交通过不需要特判任何边界情况。target小于所有元素时整个循环里nums[mid]都targetright会一直向左收缩最终leftright0target大于所有元素时每次nums[mid] targetleft一直向右移动最终leftrightnums.size()。3.2 Python版本实现如果面试用Python代码几乎一样class Solution: def searchInsert(self, nums: List[int], target: int) - int: left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid return leftPython的整数没有溢出问题但为了保持模板一致性也可以用left (right - left) // 2。除此之外Python的//是向下取整mid始终靠左配合left right和left mid 1不会死循环。3.3 人类调试法手推一遍关键用例写代码容易真正理解要靠手推。拿nums [1,3,5,6]target 5来追踪初始left0right4区间[0,4) mid 0 (4-0)/2 2nums[2]5不满足nums[mid] target所以right2 区间变成[0,2) mid 0 (2-0)/2 1nums[1]3满足3 5所以left2 区间变成[2,2) left right退出循环返回2再看target 2的情况初始left0right4 mid2nums[2]55 2不成立right2 区间[0,2) mid1nums[1]33 2不成立right1 区间[0,1) mid0nums[0]11 2成立left1 区间[1,1) 退出循环返回1再看target 0初始left0right4 mid2nums[2]55 0不成立right2 mid1nums[1]33 0不成立right1 mid0nums[0]11 0不成立right0 区间[0,0) 退出循环返回0注意target 0时整个循环里left一次都没有动过right不断收缩到0。这正好符合“所有元素都大于target插入位置就是0”的预期。3.4 提交前必跑的测试用例清单我刷题时习惯先在本地把边界用例跑一遍再提交避免白白浪费提交次数。针对搜索插入位置我总结了一份测试清单测试场景输入期望输出常规命中[1,3,5,6], target52常规未命中[1,3,5,6], target21目标值小于所有元素[1,3,5,6], target00目标值大于所有元素[1,3,5,6], target74数组只有一个元素且命中[5], target50数组只有一个元素且未命中[5], target30数组只有一个元素且target大于它[5], target71空数组[], target50你可能会说空数组要特判吧不用。left0、right0while循环一次都不进直接返回0完美。这也算是左闭右开模板的一个好处所有边界情况都被统一的逻辑覆盖了不需要写if (nums.empty())这种特判。4. 新手最容易踩的坑与排查技巧4.1 死循环是怎么来的二分查找最常见的bug就是死循环。死循环的根源是区间收缩不到位或者收缩方向错误。用左闭右开模板时最容易踩的坑是把right mid写成right mid - 1。比如nums [1,3,5,6]target 0时如果right mid - 1走一遍初始left0right4 mid2nums[2]5 0right1 mid0nums[0]1 0right-1left还是0right已经-1了循环结束返回0。咦好像也没问题那如果target是数组中间值呢换个场景nums [1,3,5,6]target 4用right mid - 1写 初始left0right4 mid2nums[2]5 4right1 mid0nums[0]1 4left1 mid0nums[0]1 4left1你发现了吗left一直是1right一直是1但left right不成立循环提前结束了返回1。这个结果正好是对的但属于运气好。再想一个nums [1,3,5,6]target 6初始left0right4 mid2nums[2]5 6left3 mid3nums[3]6 6right2此时left3right2循环结束返回3。结果也是对的。好像right mid - 1也能用问题在于这道题碰巧答案都落在left的更新路径上。换一个问题比如LeetCode 34找左边界这种写法很容易出问题。与其在错误的路线上试错不如记住左闭右开模板中right mid是标配因为mid本身也可能是答案跳过它等于把答案丢了。4.2 中间值计算防溢出很多教材里写int mid (left right) / 2这在大多数题里不会出问题但极端情况下会。left和right都是int类型如果数组长度非常大比如接近int最大值leftright可能直接溢出变负数导致mid计算错误甚至数组越界访问。正确写法是int mid left (right - left) / 2。这个写法不仅防溢出逻辑上也更清晰先算出区间长度的一半再加到left上得到中间位置。C和Java刷题都用这个写法Python因为大整数不做限制写成(left right) // 2也没问题但我为了保持模板一致性还是会写left (right - left) // 2。4.3 返回left还是mid还是right很多初学者在这里犯迷糊循环结束了到底return什么先说结论左闭右开模板下return left等价于return right因为两者相等。但如果你用左闭右闭模板循环结束时left right 1此时返回left才是对的。网上有些题解返回right也没错是因为恰好在这个场景下left和right指向同一个边界。但为了不给自己埋坑建议记住左闭右开模板只写return left左闭右闭模板也只写return left。固定一种返回值别换来换去。至于为什么不return mid因为循环结束时mid可能已经不是目标位置了。mid是最后一次计算出的中间值它不一定等于插入位置。与其去分析mid是不是答案不如固定return left这个不变量。4.4 遇到重复元素时的行为差异搜索插入位置的设定里如果数组里有重复元素返回的是第一个等于target的位置。比如nums [1,3,3,3,5]target 3标准答案应该是1因为3第一次出现在下标1。左闭右开模板天然返回重复元素中最左边的位置。因为当nums[mid] target时right会收缩到mid不会跳过相等元素。如果你想找重复元素中最右边的位置需要改成nums[mid] target时left mid 1最后返回left - 1。这就是LeetCode 34里找左右边界的核心思路。这一点面试时经常被追问。你回答“我用的是一个不变量——left始终是第一个可能满足条件的位置”会比“我背了模板”显得踏实很多。4.5 一段万能排查流程如果你写完代码提交报错别急着反复提交。先在本地把mid、left、right每轮的变化打印出来。比如while (left right) { int mid left (right - left) / 2; cout left left right right mid mid endl; ... }看几轮输出问题基本就暴露了。尤其是循环次数超过预期的时候打印日志比任何静态分析都直观。我自己刷题的时候凡是二分的bug靠手推两三组数据就能定位打印只是验证。5. 从这道题出发二分变体与刷题路线5.1 四个最常用的边界问题模板搜索插入位置如果彻底理解了可以顺手总结出四个边界查找模板目标写法要点典型题目第一个 targetnums[mid] target 时 left mid 1否则 right mid搜索插入位置第一个 targetnums[mid] target 时 left mid 1否则 right mid统计大于某值的元素个数最后一个 target先求第一个 target再减一小于等于某值的最大下标最后一个 target先求第一个 target再减一前置元素查找看到没后两个都可以由前两个推导出来。所以真正要记住的核心其实只有两个第一个target和下界、上界怎么写。这个推导过程比死记四个模板有价值得多面试时你哪怕现场推面试官也会觉得你思路清晰。5.2 二分练习的推荐顺序我自己带过一些人刷题关于二分有一个相对固定的练习路线推荐给你参考LeetCode 704二分查找最基础的精确查找LeetCode 35搜索插入位置从精确查找过渡到边界查找LeetCode 34排序数组中查找元素的第一个和最后一个位置左右边界综合LeetCode 69x的平方根对整数域二分逼近LeetCode 875爱吃香蕉的狒狒对速度做二分的经典题LeetCode 410分割数组的最大值最大化最小值问题这个顺序是从“找值”到“找边界”到“找最值”的递进。尤其875和第410题这两道题已经把二分从“数组查值”拓展到“对解空间做二分”了。很多没刷过这类题的人会以为二分只能查数组其实只要满足“单调性”就能二分。搜索插入位置是这条路线里的第二站。第一站704让你学会“精确查找”到35这一题你要把思维变成“区间收缩到边界上”。这一步跨过去后面的34、69、875就不会觉得跳跃太大了。5.3 面试时怎么把二分讲清楚面试如果考到这道题光写出代码是不够的。我建议按这个顺序讲先说明“数组有序所以可以二分”然后定义自己的区间是左闭右开还是左闭右闭说清楚每轮缩小区间的依据再解释循环结束时left的含义最后用自己的test case验证边界。比如你可以说“我维护的区间是左闭右开[left, right)初始时left0rightnums.size()。每次取mid如果nums[mid]小于target说明插入位置在mid右边所以left更新为mid1否则说明mid可能是答案或答案在mid左边所以right更新为mid。循环结束后left等于插入位置。”这段话比直接甩代码更像一个“思考过边界”的候选人。面试官通常接着会问如果数组有重复元素会怎样如果要求返回第一个大于target的位置呢把上面那张表里的推导在脑中过一遍基本都能答上来。5.4 从一个模板到肌肉记忆最后说点心得。二分查找的精髓不在背模板而在于每次写之前先想清楚三件事区间是什么定义循环条件是什么收缩规则是什么只要这三件事统一代码基本不会错。我一开始刷这道题的时候用的是左闭右闭模板也没出问题但后来刷LeetCode 34找左右边界时发现左闭右闭写起来很别扭一会儿要right mid一会儿要right mid - 1容易乱。后来换成左闭右开模板一切变得清晰找左边界就是把nums[mid] target放左边收缩找右边界就是把nums[mid] target放左边收缩边界条件完全不用特判。从那以后所有“找边界”类的二分题我都统一用一套模板刷题速度明显上去了。如果你现在还在两个模板之间纠结我的建议是选择左闭右开然后一个月内所有二分题都用它把它写到肌肉记忆里。等熟练了再尝试去理解另一个模板你会发现两者本质是一样的只是区间定义不同。这道题确实不难它难在让你真正理解二分查找的不变量。把“left是第一个可能满足条件的位置”这个念头刻进脑子里遇到任何二分变体你都不会慌。接下来就可以放心去刷LeetCode 34、875、410了。
搜索插入位置：从LeetCode 35吃透二分查找边界模板
这道题我在LeetCode热题100里刷到的时候第一反应是“这也太简单了吧”结果越写越发现搜索插入位置其实是二分查找里最容易被低估的一道题。它表面上只要求你找到一个插入下标实际上考察的是你对“二分查找终止状态”的理解是面试官最爱拿来试探你边界功底的那类题目。先说清楚这道题是什么给定一个排序数组和一个目标值如果在数组里找到了目标值返回它的下标如果没找到返回它按顺序应该被插入的位置。LeetCode原题编号是35在热门100题单里通常被排在第63位所以标题里写成“63搜索插入位置”。它属于典型的二分查找入门题但也是一堆二分变题的母题从“爱吃香蕉的狒狒”到各种“最大化最小值”问题根子都在这道题的理解上。适合两类人看一类是刚接触二分、被各种边界搞晕的新手另一类是刷了几十道二分题但总在写right mid还是right mid - 1之间犹豫的同学。1. 把题目拆开看它真正考的是什么1.1 题目描述与本质重构原题给了一个升序排列的整数数组nums和一个目标值target要求返回target在数组中的索引如果不存在就返回它会被按顺序插入的位置。运行时间复杂度要求O(log n)。举个例子nums [1,3,5,6]target 5时返回2target 2时返回1因为2应该插在下标1的位置target 7时返回4因为7比所有元素都大要插在末尾。很多新手盯着“插入位置”这四个字会下意识想“我得先判断target在不在数组里不在的话再找插哪”。这是线性思维。实际上你可以把整个问题统一成一个更简洁的表述在数组nums中找到第一个大于等于target的元素下标如果所有元素都小于target则返回数组长度。这句话一出来问题就变味了——它不再是“查找条件判断”两件事而是一个纯粹的“边界位置查找”问题。而“查找第一个满足条件的位置”正是二分查找最擅长的场景。1.2 为什么线性查找不行如果你用暴力解法从数组头开始遍历找到第一个大于等于target的位置就停最坏情况下要遍历整个数组时间复杂度O(n)。而数组是有序的这个前提条件意味着我们可以利用“跳过一半”的策略。二分查找的时间复杂度是O(log n)。假设数组长度是100万线性查找最坏要比较100万次二分查找只需要20次左右。这差距在单次查询上可能感觉不出来但如果查询很多次或者在系统里处理海量数据O(log n)就是唯一能扛住的选择。从面试角度来说题目已经明确写了“时间复杂度O(log n)”或者面试官口头要求那基本就是直接暗示二分。如果题目没写这个要求看到“排序数组”这个关键词第一反应也应该是二分。1.3 从这道题延伸出的经典变体搜索插入位置本身不复杂但它是各种二分变题的地基。我随便列几个相关的在排序数组中查找元素的第一个和最后一个位置LeetCode 34求平方根LeetCode 69用二分逼近整数平方根爱吃香蕉的狒狒LeetCode 875对速度值做二分分割数组的最大值LeetCode 410典型的最大化最小值这些题目里LeetCode 34直接就是“找左边界找右边界”本质就是搜索插入位置的升级版LeetCode 875需要对“速度”这个连续值域做二分和搜索插入位置在“找边界”这个思维上一脉相承。所以你别看这道题写起来就十几行代码把它彻底吃透后面一大片二分题都会轻松很多。2. 二分查找的核心原理与区间模板2.1 二分的本质让候选区间每轮减半讲二分之前总有人问我“二分到底难在哪”。我觉得难在两点一是边界条件二是区间定义。很多人写二分靠背代码边界一换就懵。这里先讲本质。二分查找的思路是在一个有序区间里维护一个“可能包含答案”的范围每轮取中间位置的值根据这个值和目标值的关系把范围缩小一半。关键在于你选的那个“中间值”到底落在区间内的哪个位置以及区间在什么情况下变成空集或者收敛到一个位置。不用把它想得高端。你猜一个1到100之间的数字别人只告诉你“大了”还是“小了”你用二分策略最多7次就能猜中。这个过程中你每次猜的数就是mid剩下的范围就是候选区间。搜索插入位置也一样只是“找某个值”变成了“找第一个不小于target的位置”。2.2 模板一左闭右闭区间先看最常见的模板也就是许多人背过的左闭右闭写法int searchInsert(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }在这个模板里区间[left, right]始终保持“两端都包含”的定义。因为左右都是闭区间所以当mid不是答案时必须将区间收缩到mid1或mid-1否则下一次循环又会把mid包含进去造成死循环。循环结束的条件是left right也就是区间变成空集。这时候left指向的位置就是target应该插入的位置。原理是最后一次出现nums[mid] target时left移到了mid1而所有比target小的元素都在left左边最后一次出现nums[mid] target时right移到了mid-1所有比target大的元素都在right右边。最终left就是“第一个不小于target的下标”。2.3 模板二左闭右开区间我实际写题更常用的是另一个模板左闭右开int searchInsert(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }这个模板有几个鲜明的特点right初始化为nums.size()不包含在候选区间里所以模拟的是区间[left, right)循环条件是left right因为区间永远非空就没有必要等到left rightnums[mid] target时mid肯定不是答案继续找右边left mid 1nums[mid] target时mid可能是答案也可能答案在更左边所以right mid不能跳过mid循环结束时left right这个位置就是要找的边界。很多人一开始不太适应这种写法觉得“怎么没有equal分支”。这个模板的核心思路是不管target存不存在找的都是“第一个大于等于target的位置”。没有显式的相等判断因为“等于”也属于“大于等于”的一部分只需要把等于的情况和大于的情况一起归入right mid。2.4 两个模板怎么选核心判断标准就是你要找的是“精确等于某个值”还是“第一个满足某条件的位置”。如果只是找target是否存在两个模板都行但左闭右闭写法更直观因为相等直接返回。如果找的是边界、插入点、左边界、右边界这类问题左闭右开写法更不容易写错因为它天然保持“left永远指向可行区间左侧右边界”的不变量。我个人的偏好是涉及“找边界”的题目一律用左闭右开模板涉及“精确查值”的题目用左闭右闭模板。搜索插入位置属于“找边界”用左闭右开模板最顺手。3. 代码实现与完整调试记录3.1 C实现与逐行注释用C写左闭右开模板的完整代码class Solution { public: int searchInsert(vectorint nums, int target) { int left 0; int right nums.size(); // 左闭右开区间 [left, right) while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { // mid 位置的元素小于 target说明插入位置在 mid 右侧 left mid 1; } else { // mid 位置的元素大于等于 target说明插入位置可能是 mid 或更靠左 right mid; } } return left; // 循环结束时 left right就是插入位置 } };第8行用left (right - left) / 2而不是(left right) / 2是为了防止leftright溢出。第13行是二分的精髓遇到nums[mid] target就把左边界收缩到mid1因为mid位置的值太小不可能是插入点遇到nums[mid] target就把右边界收缩到mid因为mid本身有可能就是答案不能排除。这个模板在LeetCode 35上可以直接提交通过不需要特判任何边界情况。target小于所有元素时整个循环里nums[mid]都targetright会一直向左收缩最终leftright0target大于所有元素时每次nums[mid] targetleft一直向右移动最终leftrightnums.size()。3.2 Python版本实现如果面试用Python代码几乎一样class Solution: def searchInsert(self, nums: List[int], target: int) - int: left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid return leftPython的整数没有溢出问题但为了保持模板一致性也可以用left (right - left) // 2。除此之外Python的//是向下取整mid始终靠左配合left right和left mid 1不会死循环。3.3 人类调试法手推一遍关键用例写代码容易真正理解要靠手推。拿nums [1,3,5,6]target 5来追踪初始left0right4区间[0,4) mid 0 (4-0)/2 2nums[2]5不满足nums[mid] target所以right2 区间变成[0,2) mid 0 (2-0)/2 1nums[1]3满足3 5所以left2 区间变成[2,2) left right退出循环返回2再看target 2的情况初始left0right4 mid2nums[2]55 2不成立right2 区间[0,2) mid1nums[1]33 2不成立right1 区间[0,1) mid0nums[0]11 2成立left1 区间[1,1) 退出循环返回1再看target 0初始left0right4 mid2nums[2]55 0不成立right2 mid1nums[1]33 0不成立right1 mid0nums[0]11 0不成立right0 区间[0,0) 退出循环返回0注意target 0时整个循环里left一次都没有动过right不断收缩到0。这正好符合“所有元素都大于target插入位置就是0”的预期。3.4 提交前必跑的测试用例清单我刷题时习惯先在本地把边界用例跑一遍再提交避免白白浪费提交次数。针对搜索插入位置我总结了一份测试清单测试场景输入期望输出常规命中[1,3,5,6], target52常规未命中[1,3,5,6], target21目标值小于所有元素[1,3,5,6], target00目标值大于所有元素[1,3,5,6], target74数组只有一个元素且命中[5], target50数组只有一个元素且未命中[5], target30数组只有一个元素且target大于它[5], target71空数组[], target50你可能会说空数组要特判吧不用。left0、right0while循环一次都不进直接返回0完美。这也算是左闭右开模板的一个好处所有边界情况都被统一的逻辑覆盖了不需要写if (nums.empty())这种特判。4. 新手最容易踩的坑与排查技巧4.1 死循环是怎么来的二分查找最常见的bug就是死循环。死循环的根源是区间收缩不到位或者收缩方向错误。用左闭右开模板时最容易踩的坑是把right mid写成right mid - 1。比如nums [1,3,5,6]target 0时如果right mid - 1走一遍初始left0right4 mid2nums[2]5 0right1 mid0nums[0]1 0right-1left还是0right已经-1了循环结束返回0。咦好像也没问题那如果target是数组中间值呢换个场景nums [1,3,5,6]target 4用right mid - 1写 初始left0right4 mid2nums[2]5 4right1 mid0nums[0]1 4left1 mid0nums[0]1 4left1你发现了吗left一直是1right一直是1但left right不成立循环提前结束了返回1。这个结果正好是对的但属于运气好。再想一个nums [1,3,5,6]target 6初始left0right4 mid2nums[2]5 6left3 mid3nums[3]6 6right2此时left3right2循环结束返回3。结果也是对的。好像right mid - 1也能用问题在于这道题碰巧答案都落在left的更新路径上。换一个问题比如LeetCode 34找左边界这种写法很容易出问题。与其在错误的路线上试错不如记住左闭右开模板中right mid是标配因为mid本身也可能是答案跳过它等于把答案丢了。4.2 中间值计算防溢出很多教材里写int mid (left right) / 2这在大多数题里不会出问题但极端情况下会。left和right都是int类型如果数组长度非常大比如接近int最大值leftright可能直接溢出变负数导致mid计算错误甚至数组越界访问。正确写法是int mid left (right - left) / 2。这个写法不仅防溢出逻辑上也更清晰先算出区间长度的一半再加到left上得到中间位置。C和Java刷题都用这个写法Python因为大整数不做限制写成(left right) // 2也没问题但我为了保持模板一致性还是会写left (right - left) // 2。4.3 返回left还是mid还是right很多初学者在这里犯迷糊循环结束了到底return什么先说结论左闭右开模板下return left等价于return right因为两者相等。但如果你用左闭右闭模板循环结束时left right 1此时返回left才是对的。网上有些题解返回right也没错是因为恰好在这个场景下left和right指向同一个边界。但为了不给自己埋坑建议记住左闭右开模板只写return left左闭右闭模板也只写return left。固定一种返回值别换来换去。至于为什么不return mid因为循环结束时mid可能已经不是目标位置了。mid是最后一次计算出的中间值它不一定等于插入位置。与其去分析mid是不是答案不如固定return left这个不变量。4.4 遇到重复元素时的行为差异搜索插入位置的设定里如果数组里有重复元素返回的是第一个等于target的位置。比如nums [1,3,3,3,5]target 3标准答案应该是1因为3第一次出现在下标1。左闭右开模板天然返回重复元素中最左边的位置。因为当nums[mid] target时right会收缩到mid不会跳过相等元素。如果你想找重复元素中最右边的位置需要改成nums[mid] target时left mid 1最后返回left - 1。这就是LeetCode 34里找左右边界的核心思路。这一点面试时经常被追问。你回答“我用的是一个不变量——left始终是第一个可能满足条件的位置”会比“我背了模板”显得踏实很多。4.5 一段万能排查流程如果你写完代码提交报错别急着反复提交。先在本地把mid、left、right每轮的变化打印出来。比如while (left right) { int mid left (right - left) / 2; cout left left right right mid mid endl; ... }看几轮输出问题基本就暴露了。尤其是循环次数超过预期的时候打印日志比任何静态分析都直观。我自己刷题的时候凡是二分的bug靠手推两三组数据就能定位打印只是验证。5. 从这道题出发二分变体与刷题路线5.1 四个最常用的边界问题模板搜索插入位置如果彻底理解了可以顺手总结出四个边界查找模板目标写法要点典型题目第一个 targetnums[mid] target 时 left mid 1否则 right mid搜索插入位置第一个 targetnums[mid] target 时 left mid 1否则 right mid统计大于某值的元素个数最后一个 target先求第一个 target再减一小于等于某值的最大下标最后一个 target先求第一个 target再减一前置元素查找看到没后两个都可以由前两个推导出来。所以真正要记住的核心其实只有两个第一个target和下界、上界怎么写。这个推导过程比死记四个模板有价值得多面试时你哪怕现场推面试官也会觉得你思路清晰。5.2 二分练习的推荐顺序我自己带过一些人刷题关于二分有一个相对固定的练习路线推荐给你参考LeetCode 704二分查找最基础的精确查找LeetCode 35搜索插入位置从精确查找过渡到边界查找LeetCode 34排序数组中查找元素的第一个和最后一个位置左右边界综合LeetCode 69x的平方根对整数域二分逼近LeetCode 875爱吃香蕉的狒狒对速度做二分的经典题LeetCode 410分割数组的最大值最大化最小值问题这个顺序是从“找值”到“找边界”到“找最值”的递进。尤其875和第410题这两道题已经把二分从“数组查值”拓展到“对解空间做二分”了。很多没刷过这类题的人会以为二分只能查数组其实只要满足“单调性”就能二分。搜索插入位置是这条路线里的第二站。第一站704让你学会“精确查找”到35这一题你要把思维变成“区间收缩到边界上”。这一步跨过去后面的34、69、875就不会觉得跳跃太大了。5.3 面试时怎么把二分讲清楚面试如果考到这道题光写出代码是不够的。我建议按这个顺序讲先说明“数组有序所以可以二分”然后定义自己的区间是左闭右开还是左闭右闭说清楚每轮缩小区间的依据再解释循环结束时left的含义最后用自己的test case验证边界。比如你可以说“我维护的区间是左闭右开[left, right)初始时left0rightnums.size()。每次取mid如果nums[mid]小于target说明插入位置在mid右边所以left更新为mid1否则说明mid可能是答案或答案在mid左边所以right更新为mid。循环结束后left等于插入位置。”这段话比直接甩代码更像一个“思考过边界”的候选人。面试官通常接着会问如果数组有重复元素会怎样如果要求返回第一个大于target的位置呢把上面那张表里的推导在脑中过一遍基本都能答上来。5.4 从一个模板到肌肉记忆最后说点心得。二分查找的精髓不在背模板而在于每次写之前先想清楚三件事区间是什么定义循环条件是什么收缩规则是什么只要这三件事统一代码基本不会错。我一开始刷这道题的时候用的是左闭右闭模板也没出问题但后来刷LeetCode 34找左右边界时发现左闭右闭写起来很别扭一会儿要right mid一会儿要right mid - 1容易乱。后来换成左闭右开模板一切变得清晰找左边界就是把nums[mid] target放左边收缩找右边界就是把nums[mid] target放左边收缩边界条件完全不用特判。从那以后所有“找边界”类的二分题我都统一用一套模板刷题速度明显上去了。如果你现在还在两个模板之间纠结我的建议是选择左闭右开然后一个月内所有二分题都用它把它写到肌肉记忆里。等熟练了再尝试去理解另一个模板你会发现两者本质是一样的只是区间定义不同。这道题确实不难它难在让你真正理解二分查找的不变量。把“left是第一个可能满足条件的位置”这个念头刻进脑子里遇到任何二分变体你都不会慌。接下来就可以放心去刷LeetCode 34、875、410了。