阅前提示本文不含任何平台名称与真实人物信息仅讨论算法本身与通用解法。题目编号“66”指某热门题库中的第66道题建议结合自身刷题进度按需参考。如果你刷题已经刷到二分查找这一块大概率会撞上这道“搜索插入位置”。它的名气不在于难而在于它把二分查找里最容易踩坑的那几个细节——边界怎么定、mid怎么取、循环条件怎么写——全部浓缩在一道题里。很多新手在这道题上栽跟头转头去翻题解看到各种版本的二分解法更懵了同样是二分为什么有的写left right有的写left right有的返回left有的返回mid到底哪个是对的这篇文章不打算给你抄代码就完事而是把这道题从题意到边界处理再到往后的变体题型全部掰开揉碎讲清楚。你会发现搞定这一道题等于把二分查找的“查找边界”这一整个系列都给打通了。1. 题目核心拆解它到底在问什么先看题目描述。给定一个排序数组和一个目标值如果目标值存在于数组中返回它的索引如果不存在返回它按顺序应该被插入的位置。要求时间复杂度为 O(log n)。1.1 一个例子看懂题目数组nums [1, 3, 5, 6]目标值target 5。因为 5 在数组里下标是 2所以返回 2。这是“命中”的情况。如果target 22 不在数组里它应该插在 1 和 3 之间也就是下标 1 的位置。这是“未命中但有比它小的元素”的情况。如果target 77 比数组里所有元素都大应该插在末尾即下标 4。这是“超过最大值”的情况。如果target 00 比数组里所有元素都小应该插在开头即下标 0。这是“小于最小值”的情况。四种情况一摆出来题目的本质就很清楚了你其实不是在找 target 本身而是在找数组中第一个大于等于 target 的元素位置。1.2 为什么不能用遍历看到排序数组很多人的第一反应是直接 for 循环从头扫一遍找到 target 就返回下标找不到就找第一个比 target 大的位置。这确实能做对但时间复杂度是 O(n)不符合题目的 O(log n) 要求。在真实场景里如果一个有序数组的长度是百万级别线性扫描的平均耗时是二分查找的几千倍。这也是刷题之外的实际意义排序数据结构的核心优势就是可以利用有序性进行快速查找不需要老老实实遍历。这一题就是强制你放弃 O(n) 的思维学会利用有序性砍掉一半的搜索空间。2. 二分查找的核心思路为什么它是对的二分查找的原理并不复杂。一个有序数组取中间位置的值和目标值比较如果中间值小于目标值说明目标值只可能出现在右半部分如果中间值大于目标值说明目标值只可能出现在左半部分。每次比较都能排除一半的数据所以时间复杂度是 O(log n)。2.1 让“插入位置”指代一个具体的索引这道题最核心的一个思维转换在于插入位置本质上是一个具体的下标值而我们要找的就是这个下标。比方说nums [1, 3, 5, 6]target 2。2 应该插在下标 1 的位置所以我们想找的答案是 1。这里的 1 意味着“2 应该占据的位置”。换个角度想我们要找的是数组中第一个不小于 2 的元素所在的位置。数组里第一个不小于 2 的元素是 3它的下标是 1所以答案就是 1。再想深一层如果 target 5找第一个不小于 5 的元素那就是 5 自己下标是 2答案也是 2。这就统一了“命中”和“未命中”两种情况我们全程只需要做一件事找第一个大于等于 target 的位置。这个位置就是插入位置也就是标准库中 lower_bound 的实现逻辑。2.2 为什么二分可以持续收敛到正确答案假设我们维护一个区间[left, right]这个区间包含我们要找的答案。每次取中间位置 mid比较 nums[mid] 与 target如果nums[mid] target说明 mid 位置上的元素比 target 小。由于数组有序mid 左边所有元素也都比 target 小所以答案一定在 mid 的右边。我们把区间缩小为[mid 1, right]。如果nums[mid] target说明 mid 位置上的元素不小于 targetmid 有可能就是答案也有可能是比答案更大的位置。但至少能确定答案不会在 mid 的右边。我们把区间缩小为[left, mid]。这个过程反复进行区间不断缩小最终 left 和 right 重合那个位置就是答案。这个思路就是二分查找处理“边界问题”的经典姿势不是找相等的点而是找边界点。3. 两种主流写法的选择左闭右闭 vs 左闭右开这是刷题社区里吵得最凶的一个话题。同样是二分有人习惯写left right有人习惯写left right。两种写法都能 AC但对应的心智模型完全不同。这道题我建议你重点掌握左闭右闭的写法因为它的边界条件最直观也最接近你对“数组下标”的直觉。3.1 左闭右闭写法的完整推导左闭右闭的含义是每次循环时搜索区间是[left, right]两个端点都可能成为答案。初始时left 0right nums.length - 1。注意这里 right 初始为最后一个元素的下标意味着我们一开始认为答案可能在数组的任意位置包括最后一个位置。循环条件是while (left right)为什么是因为当 left 和 right 相等时区间内还有一个元素需要判断不能直接退出。每次循环mid left (right - left) / 2。这里不写(left right) / 2是为了防止两个大数相加时溢出虽然这道题不太可能触发但这是一个值得养成的习惯。判断逻辑分两种情况public int searchInsert(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }这段代码的核心逻辑就是找到“第一个大于等于 target 的位置”。我来逐行解释为什么这样写是对的为什么最后返回的是 left。当nums[mid] target时说明 mid 及 mid 左边所有的数都小于 target它们都不可能是答案。所以答案的最小可能位置是 mid 1于是把左边界收缩到 mid 1。当nums[mid] target时说明 mid 有可能是答案也有可能是比答案更偏右的位置。因此答案不可能在 mid 的右边我们需要把右边界收缩到 mid - 1而不是 mid。这里为什么要减 1因为我们已经检查过 mid 了即使 mid 是答案也不会因为把 right 缩到 mid - 1 而丢失——答案只会出现在 left 到 mid - 1 的范围内或者更准确地说left 最终会收敛到答案。循环退出时left right此时 left 指向的位置就是第一个大于等于 target 的位置。为什么返回 left 一定是对的可以分几种情况验证target 在数组中存在比如 nums [1, 3, 5, 6]target 5。二分过程中会找到 5 的下标 2但循环并不会在这里停下返回而是继续收缩区间。最终 left 会停在 2 的位置因为这是一个“第一个大于等于 5”的元素。target 不存在且位于两个元素之间比如 target 2。最终 left 会停在 1 的位置因为 3 是第一个大于等于 2 的元素。target 大于所有元素比如 target 7。此时 nums[mid] target 一直成立left 一直右移最后 left 等于 4也就是 nums.length这正是“插入到末尾”的位置合法。target 小于所有元素比如 target 0。此时 nums[mid] target 一直成立right 一直左移最后 left 停在 0合法。3.2 左闭右开写法的区别与场景public int searchInsert(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }这段代码的区间含义是[left, right)right 不包含在搜索范围内。初始 right nums.length表示最后一个元素的后面那个位置也在候选范围内。当nums[mid] target时right mid而不是 mid - 1因为右边界是开区间mid 仍然需要被保留在下一次的搜索范围内。两种写法最终返回的都是 left核心逻辑完全等价。左闭右开的写法在 C 的 STL 中被广泛使用因为迭代器的 end() 天然就是开区间。如果你主要写 Java 或 Python建议先精通左闭右闭的写法再去理解左闭右开否则容易混淆。3.3 两种写法的对比总结比较维度左闭右闭左闭右开区间表示[left, right][left, right)初始 rightnums.length - 1nums.length循环条件left rightleft rightnums[mid] target 时的处理right mid - 1right mid返回位置leftleft适用场景数组下标明确的常规场景迭代器、STL、部分语言惯用法两种写法没有绝对的优劣但如果你两种都学很容易在细节上绊倒。我的建议是先认准一种写法练熟再了解另一种写法用于阅读他人代码。不要交替着写不然半夜 debug 的时候很容易怀疑人生。4. 代码实现与细节打磨思路清楚了代码写起来就很顺。我用三种语言分别给出一版实现都基于左闭右闭的逻辑。4.1 Python 实现def search_insert(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return leftPython 的//是整数除法天然向下取整。这里不需要担心溢出问题Python 的整数是任意精度的。4.2 Java 实现public int searchInsert(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }left (right - left) / 2是为了防止 left right 溢出。虽然现在的数组长度一般达不到 int 上限但这个写法是一个好习惯。4.3 C 实现class Solution { public: 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) { left mid 1; } else { right mid - 1; } } return left; } };C 里nums.size()返回的是无符号整数如果你写int right nums.size() - 1在某些编译器下会有符号转换警告。稳妥的做法是强转成 int例如int right (int)nums.size() - 1。不过 LeetCode 风格的代码通常直接赋值也能通过编译只是我们写工程代码时要注意这一点。5. 变体题型一道题打通一个系列这道题之所以被放进热门题单是因为它延伸出来的变体非常多。我把常见的几个变体列出来你会发现它们的核心逻辑完全一致只是返回条件和细节判断不同。5.1 查找第一个大于等于 target 的位置这其实就是本题的原始逻辑不需要额外处理。上面的代码已经实现了这个功能。5.2 查找第一个大于 target 的位置这个变体要求找严格大于 target 的第一个位置。核心区别在于当nums[mid] target时我们不能把 left 收缩到 mid 1 之外的位置但答案有可能在 mid 的右边。所以判断逻辑改为def first_greater(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return left注意判断条件是nums[mid] target而不是 target。等于 target 的元素不算“大于”所以也要把 left 右移去找更右边的元素。5.3 查找最后一个小于等于 target 的位置这个变体对应的是“插入位置 - 1”也就是 target 应该插在哪个元素后面。把普通查找的目标反过来当nums[mid] target时说明 mid 可能是答案需要把 left 移到 mid 1 继续找更靠右的满足条件的元素当nums[mid] target时把 right 移到 mid - 1。最终返回 right。这个变体在很多实际问题中都有用到。比如给定一组时间戳查找最后一个不超过当前时间的时间点就是在“最后一个小于等于 target”的位置上做文章。5.4 查找左右边界经典二分边界题如果题目变成“查找第一个等于 target 的位置”和“查找最后一个等于 target 的位置”处理方式就需要区分等号。查找第一个等于 target 的位置nums[mid] target时收缩右边界最终返回的 left 再校验一下是否等于 target。查找最后一个等于 target 的位置nums[mid] target时收缩左边界最终返回的 right 再校验一下是否等于 target。这两种写法配合起来就是经典“在排序数组中查找元素的第一个和最后一个位置”题目的解法核心。你会发现这些题和本题是同一个知识体系理解了本题的边界收缩逻辑那些题基本就是改一个等号的事。6. 实际刷题中的常见问题与排查心得这道题虽然简单但在实际写代码和 debug 的过程中有些问题反复出现。我把它们集中整理一下方便你对照自查。6.1 死循环问题死循环的根源几乎都出在mid的取值和区间收缩不匹配上尤其是左闭右开写法中如果right更新为mid而mid又等于left区间就可能永远不缩小。举个例子某写法在nums[mid] target时执行right mid但循环条件是while (left right)这时如果left mid right更新后right不变left也不变就无限循环了。这种情况大概率是混用了两种写法的区间规则导致的。经验之谈如果用左闭右开写法就全程贯彻左闭右开。不要用left right的循环条件去配right mid的收缩方式。写之前先在心里明确区间到底包含哪些下标再动手。6.2 返回值总是偏差 1很多初学者最后返回mid而不是left导致某些测试用例结果不对。你会发现当 target 存在时返回 mid 可能碰巧是对的但 target 不存在时就会出错。原理很简单循环结束是因为区间被压缩到空此时 left 指向的才是第一个大于等于 target 的位置而 mid 是最后一次计算的位置它可能落在答案的左边或右边。所以正确的返回值永远是区间压缩后的边界也就是 left左闭右闭或 left左闭右开而不是 mid。6.3 数组为空的情况怎么处理如果 nums 为空数组right nums.length - 1 -1循环直接跳过返回 left 0。这个结果是正确的因为空数组的插入位置只能是 0。所以这题不需要特殊处理空数组但你要明白为什么代码天然兼容这种情况。6.4 单独验证四个边界情况刷完这道题我建议你在本地把这四个测试用例全部跑一遍用例numstarget预期输出常规命中[1, 3, 5, 6]52常规未命中[1, 3, 5, 6]21大于所有元素[1, 3, 5, 6]74小于所有元素[1, 3, 5, 6]00这四个用例分别对应“命中”、“插入中间”、“插入末尾”、“插入开头”四种情况。如果四个用例都通过代码基本就稳了。6.5 用“区间不变量”校验代码正确性这是我 debug 时最常用的一招——写二分题的时候在心里或者注释里明确一个“不变量”也就是每次循环开始前答案一定在[left, right]范围内。然后每次更新 left 或 right 时检查一下新区间是否仍然包含答案。比如左闭右闭解法中当nums[mid] target时把 left 设为 mid 1这一步可以理解为“答案一定不在 mid 及其左侧所以新的搜索区间是 [mid 1, right]”。当nums[mid] target时把 right 设为 mid - 1这一步可以理解为“mid 已经检查过了答案最多到 mid因此搜索区间是 [left, mid - 1]”。只要这个不变量始终成立循环结束时答案就在 left 和 right 重合的位置也就是 left。7. 从刷题到工程这道题的真实用处有人觉得刷这种题只是面试用现实中写业务代码根本碰不到。这个说法对了一半二分查找的“形态”不常见但“在一个有序序列里快速定位边界”的思想到处都在用。7.1 真实场景一版本号区间查找假设你在做一个配置系统每个配置项都有一个生效的版本号配置按版本号升序排列。用户请求某个版本的功能开关时需要快速找到当前版本应该应用哪一条配置。这个“找最后一个小于等于当前版本号的位置”的操作本质就是二分查找的变体。7.2 真实场景二时间戳记录查询一个埋点系统按时间戳存储日志需要查询某个时刻之前最近的一条记录用的就是“最后一个小于等于 target”的逻辑。如果数据量到达亿级别线性扫描是不可接受的二分查找配合有序索引几乎是最优解。7.3 真实场景三分数的等级划分给定一份分数区间表[0, 60) 是不及格[60, 75) 是及格[75, 90) 是良好[90, 100] 是优秀。把每个分数映射到等级本质上就是在区间边界数组中做一次二分查找找到这个分数落在哪个区间里。这不就是“搜索插入位置”的现实映射吗所以不要小看这道题它不仅仅是二分查找的练习题更是一把打开“有序数据快速检索”大门的钥匙。把这个边界收缩逻辑吃透以后遇到任何“在有序数据中找边界”的问题你都能条件反射地写出二分。8. 收尾这道题值得多花点时间最后分享一点我在做这道题时的体会。这道题我前前后后写过不下五遍每次隔一段时间重写还是会犯一些小错误。后来我总结出原因二分查找的模板并不难背难的是每次都能想明白区间收缩的“为什么”。我个人的建议是不要急着背代码而是拿一张纸手动模拟一遍[1, 3, 5, 6]中查找 target 2 的过程每一步都写下 left、right、mid 的值以及为什么更新 left 或 right。手动模拟两三次之后你对边界条件的理解会有一个质变。如果你能把这道题的左闭右闭和左闭右开两种写法都理解透彻并且能独立推导出“查找第一个大于 target”和“查找最后一个小于等于 target”的代码那么二分查找这一关你就真正迈过去了。后续再遇到任何二分变体你都不会再慌。 
长河君 · 2026/10/13 23:33:56 · 阅读 1.2k 二分查找边界处理全解：从搜索插入位置到左右边界变体
阅前提示本文不含任何平台名称与真实人物信息仅讨论算法本身与通用解法。题目编号“66”指某热门题库中的第66道题建议结合自身刷题进度按需参考。如果你刷题已经刷到二分查找这一块大概率会撞上这道“搜索插入位置”。它的名气不在于难而在于它把二分查找里最容易踩坑的那几个细节——边界怎么定、mid怎么取、循环条件怎么写——全部浓缩在一道题里。很多新手在这道题上栽跟头转头去翻题解看到各种版本的二分解法更懵了同样是二分为什么有的写left right有的写left right有的返回left有的返回mid到底哪个是对的这篇文章不打算给你抄代码就完事而是把这道题从题意到边界处理再到往后的变体题型全部掰开揉碎讲清楚。你会发现搞定这一道题等于把二分查找的“查找边界”这一整个系列都给打通了。1. 题目核心拆解它到底在问什么先看题目描述。给定一个排序数组和一个目标值如果目标值存在于数组中返回它的索引如果不存在返回它按顺序应该被插入的位置。要求时间复杂度为 O(log n)。1.1 一个例子看懂题目数组nums [1, 3, 5, 6]目标值target 5。因为 5 在数组里下标是 2所以返回 2。这是“命中”的情况。如果target 22 不在数组里它应该插在 1 和 3 之间也就是下标 1 的位置。这是“未命中但有比它小的元素”的情况。如果target 77 比数组里所有元素都大应该插在末尾即下标 4。这是“超过最大值”的情况。如果target 00 比数组里所有元素都小应该插在开头即下标 0。这是“小于最小值”的情况。四种情况一摆出来题目的本质就很清楚了你其实不是在找 target 本身而是在找数组中第一个大于等于 target 的元素位置。1.2 为什么不能用遍历看到排序数组很多人的第一反应是直接 for 循环从头扫一遍找到 target 就返回下标找不到就找第一个比 target 大的位置。这确实能做对但时间复杂度是 O(n)不符合题目的 O(log n) 要求。在真实场景里如果一个有序数组的长度是百万级别线性扫描的平均耗时是二分查找的几千倍。这也是刷题之外的实际意义排序数据结构的核心优势就是可以利用有序性进行快速查找不需要老老实实遍历。这一题就是强制你放弃 O(n) 的思维学会利用有序性砍掉一半的搜索空间。2. 二分查找的核心思路为什么它是对的二分查找的原理并不复杂。一个有序数组取中间位置的值和目标值比较如果中间值小于目标值说明目标值只可能出现在右半部分如果中间值大于目标值说明目标值只可能出现在左半部分。每次比较都能排除一半的数据所以时间复杂度是 O(log n)。2.1 让“插入位置”指代一个具体的索引这道题最核心的一个思维转换在于插入位置本质上是一个具体的下标值而我们要找的就是这个下标。比方说nums [1, 3, 5, 6]target 2。2 应该插在下标 1 的位置所以我们想找的答案是 1。这里的 1 意味着“2 应该占据的位置”。换个角度想我们要找的是数组中第一个不小于 2 的元素所在的位置。数组里第一个不小于 2 的元素是 3它的下标是 1所以答案就是 1。再想深一层如果 target 5找第一个不小于 5 的元素那就是 5 自己下标是 2答案也是 2。这就统一了“命中”和“未命中”两种情况我们全程只需要做一件事找第一个大于等于 target 的位置。这个位置就是插入位置也就是标准库中 lower_bound 的实现逻辑。2.2 为什么二分可以持续收敛到正确答案假设我们维护一个区间[left, right]这个区间包含我们要找的答案。每次取中间位置 mid比较 nums[mid] 与 target如果nums[mid] target说明 mid 位置上的元素比 target 小。由于数组有序mid 左边所有元素也都比 target 小所以答案一定在 mid 的右边。我们把区间缩小为[mid 1, right]。如果nums[mid] target说明 mid 位置上的元素不小于 targetmid 有可能就是答案也有可能是比答案更大的位置。但至少能确定答案不会在 mid 的右边。我们把区间缩小为[left, mid]。这个过程反复进行区间不断缩小最终 left 和 right 重合那个位置就是答案。这个思路就是二分查找处理“边界问题”的经典姿势不是找相等的点而是找边界点。3. 两种主流写法的选择左闭右闭 vs 左闭右开这是刷题社区里吵得最凶的一个话题。同样是二分有人习惯写left right有人习惯写left right。两种写法都能 AC但对应的心智模型完全不同。这道题我建议你重点掌握左闭右闭的写法因为它的边界条件最直观也最接近你对“数组下标”的直觉。3.1 左闭右闭写法的完整推导左闭右闭的含义是每次循环时搜索区间是[left, right]两个端点都可能成为答案。初始时left 0right nums.length - 1。注意这里 right 初始为最后一个元素的下标意味着我们一开始认为答案可能在数组的任意位置包括最后一个位置。循环条件是while (left right)为什么是因为当 left 和 right 相等时区间内还有一个元素需要判断不能直接退出。每次循环mid left (right - left) / 2。这里不写(left right) / 2是为了防止两个大数相加时溢出虽然这道题不太可能触发但这是一个值得养成的习惯。判断逻辑分两种情况public int searchInsert(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }这段代码的核心逻辑就是找到“第一个大于等于 target 的位置”。我来逐行解释为什么这样写是对的为什么最后返回的是 left。当nums[mid] target时说明 mid 及 mid 左边所有的数都小于 target它们都不可能是答案。所以答案的最小可能位置是 mid 1于是把左边界收缩到 mid 1。当nums[mid] target时说明 mid 有可能是答案也有可能是比答案更偏右的位置。因此答案不可能在 mid 的右边我们需要把右边界收缩到 mid - 1而不是 mid。这里为什么要减 1因为我们已经检查过 mid 了即使 mid 是答案也不会因为把 right 缩到 mid - 1 而丢失——答案只会出现在 left 到 mid - 1 的范围内或者更准确地说left 最终会收敛到答案。循环退出时left right此时 left 指向的位置就是第一个大于等于 target 的位置。为什么返回 left 一定是对的可以分几种情况验证target 在数组中存在比如 nums [1, 3, 5, 6]target 5。二分过程中会找到 5 的下标 2但循环并不会在这里停下返回而是继续收缩区间。最终 left 会停在 2 的位置因为这是一个“第一个大于等于 5”的元素。target 不存在且位于两个元素之间比如 target 2。最终 left 会停在 1 的位置因为 3 是第一个大于等于 2 的元素。target 大于所有元素比如 target 7。此时 nums[mid] target 一直成立left 一直右移最后 left 等于 4也就是 nums.length这正是“插入到末尾”的位置合法。target 小于所有元素比如 target 0。此时 nums[mid] target 一直成立right 一直左移最后 left 停在 0合法。3.2 左闭右开写法的区别与场景public int searchInsert(int[] nums, int target) { int left 0, right nums.length; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }这段代码的区间含义是[left, right)right 不包含在搜索范围内。初始 right nums.length表示最后一个元素的后面那个位置也在候选范围内。当nums[mid] target时right mid而不是 mid - 1因为右边界是开区间mid 仍然需要被保留在下一次的搜索范围内。两种写法最终返回的都是 left核心逻辑完全等价。左闭右开的写法在 C 的 STL 中被广泛使用因为迭代器的 end() 天然就是开区间。如果你主要写 Java 或 Python建议先精通左闭右闭的写法再去理解左闭右开否则容易混淆。3.3 两种写法的对比总结比较维度左闭右闭左闭右开区间表示[left, right][left, right)初始 rightnums.length - 1nums.length循环条件left rightleft rightnums[mid] target 时的处理right mid - 1right mid返回位置leftleft适用场景数组下标明确的常规场景迭代器、STL、部分语言惯用法两种写法没有绝对的优劣但如果你两种都学很容易在细节上绊倒。我的建议是先认准一种写法练熟再了解另一种写法用于阅读他人代码。不要交替着写不然半夜 debug 的时候很容易怀疑人生。4. 代码实现与细节打磨思路清楚了代码写起来就很顺。我用三种语言分别给出一版实现都基于左闭右闭的逻辑。4.1 Python 实现def search_insert(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return leftPython 的//是整数除法天然向下取整。这里不需要担心溢出问题Python 的整数是任意精度的。4.2 Java 实现public int searchInsert(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }left (right - left) / 2是为了防止 left right 溢出。虽然现在的数组长度一般达不到 int 上限但这个写法是一个好习惯。4.3 C 实现class Solution { public: 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) { left mid 1; } else { right mid - 1; } } return left; } };C 里nums.size()返回的是无符号整数如果你写int right nums.size() - 1在某些编译器下会有符号转换警告。稳妥的做法是强转成 int例如int right (int)nums.size() - 1。不过 LeetCode 风格的代码通常直接赋值也能通过编译只是我们写工程代码时要注意这一点。5. 变体题型一道题打通一个系列这道题之所以被放进热门题单是因为它延伸出来的变体非常多。我把常见的几个变体列出来你会发现它们的核心逻辑完全一致只是返回条件和细节判断不同。5.1 查找第一个大于等于 target 的位置这其实就是本题的原始逻辑不需要额外处理。上面的代码已经实现了这个功能。5.2 查找第一个大于 target 的位置这个变体要求找严格大于 target 的第一个位置。核心区别在于当nums[mid] target时我们不能把 left 收缩到 mid 1 之外的位置但答案有可能在 mid 的右边。所以判断逻辑改为def first_greater(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return left注意判断条件是nums[mid] target而不是 target。等于 target 的元素不算“大于”所以也要把 left 右移去找更右边的元素。5.3 查找最后一个小于等于 target 的位置这个变体对应的是“插入位置 - 1”也就是 target 应该插在哪个元素后面。把普通查找的目标反过来当nums[mid] target时说明 mid 可能是答案需要把 left 移到 mid 1 继续找更靠右的满足条件的元素当nums[mid] target时把 right 移到 mid - 1。最终返回 right。这个变体在很多实际问题中都有用到。比如给定一组时间戳查找最后一个不超过当前时间的时间点就是在“最后一个小于等于 target”的位置上做文章。5.4 查找左右边界经典二分边界题如果题目变成“查找第一个等于 target 的位置”和“查找最后一个等于 target 的位置”处理方式就需要区分等号。查找第一个等于 target 的位置nums[mid] target时收缩右边界最终返回的 left 再校验一下是否等于 target。查找最后一个等于 target 的位置nums[mid] target时收缩左边界最终返回的 right 再校验一下是否等于 target。这两种写法配合起来就是经典“在排序数组中查找元素的第一个和最后一个位置”题目的解法核心。你会发现这些题和本题是同一个知识体系理解了本题的边界收缩逻辑那些题基本就是改一个等号的事。6. 实际刷题中的常见问题与排查心得这道题虽然简单但在实际写代码和 debug 的过程中有些问题反复出现。我把它们集中整理一下方便你对照自查。6.1 死循环问题死循环的根源几乎都出在mid的取值和区间收缩不匹配上尤其是左闭右开写法中如果right更新为mid而mid又等于left区间就可能永远不缩小。举个例子某写法在nums[mid] target时执行right mid但循环条件是while (left right)这时如果left mid right更新后right不变left也不变就无限循环了。这种情况大概率是混用了两种写法的区间规则导致的。经验之谈如果用左闭右开写法就全程贯彻左闭右开。不要用left right的循环条件去配right mid的收缩方式。写之前先在心里明确区间到底包含哪些下标再动手。6.2 返回值总是偏差 1很多初学者最后返回mid而不是left导致某些测试用例结果不对。你会发现当 target 存在时返回 mid 可能碰巧是对的但 target 不存在时就会出错。原理很简单循环结束是因为区间被压缩到空此时 left 指向的才是第一个大于等于 target 的位置而 mid 是最后一次计算的位置它可能落在答案的左边或右边。所以正确的返回值永远是区间压缩后的边界也就是 left左闭右闭或 left左闭右开而不是 mid。6.3 数组为空的情况怎么处理如果 nums 为空数组right nums.length - 1 -1循环直接跳过返回 left 0。这个结果是正确的因为空数组的插入位置只能是 0。所以这题不需要特殊处理空数组但你要明白为什么代码天然兼容这种情况。6.4 单独验证四个边界情况刷完这道题我建议你在本地把这四个测试用例全部跑一遍用例numstarget预期输出常规命中[1, 3, 5, 6]52常规未命中[1, 3, 5, 6]21大于所有元素[1, 3, 5, 6]74小于所有元素[1, 3, 5, 6]00这四个用例分别对应“命中”、“插入中间”、“插入末尾”、“插入开头”四种情况。如果四个用例都通过代码基本就稳了。6.5 用“区间不变量”校验代码正确性这是我 debug 时最常用的一招——写二分题的时候在心里或者注释里明确一个“不变量”也就是每次循环开始前答案一定在[left, right]范围内。然后每次更新 left 或 right 时检查一下新区间是否仍然包含答案。比如左闭右闭解法中当nums[mid] target时把 left 设为 mid 1这一步可以理解为“答案一定不在 mid 及其左侧所以新的搜索区间是 [mid 1, right]”。当nums[mid] target时把 right 设为 mid - 1这一步可以理解为“mid 已经检查过了答案最多到 mid因此搜索区间是 [left, mid - 1]”。只要这个不变量始终成立循环结束时答案就在 left 和 right 重合的位置也就是 left。7. 从刷题到工程这道题的真实用处有人觉得刷这种题只是面试用现实中写业务代码根本碰不到。这个说法对了一半二分查找的“形态”不常见但“在一个有序序列里快速定位边界”的思想到处都在用。7.1 真实场景一版本号区间查找假设你在做一个配置系统每个配置项都有一个生效的版本号配置按版本号升序排列。用户请求某个版本的功能开关时需要快速找到当前版本应该应用哪一条配置。这个“找最后一个小于等于当前版本号的位置”的操作本质就是二分查找的变体。7.2 真实场景二时间戳记录查询一个埋点系统按时间戳存储日志需要查询某个时刻之前最近的一条记录用的就是“最后一个小于等于 target”的逻辑。如果数据量到达亿级别线性扫描是不可接受的二分查找配合有序索引几乎是最优解。7.3 真实场景三分数的等级划分给定一份分数区间表[0, 60) 是不及格[60, 75) 是及格[75, 90) 是良好[90, 100] 是优秀。把每个分数映射到等级本质上就是在区间边界数组中做一次二分查找找到这个分数落在哪个区间里。这不就是“搜索插入位置”的现实映射吗所以不要小看这道题它不仅仅是二分查找的练习题更是一把打开“有序数据快速检索”大门的钥匙。把这个边界收缩逻辑吃透以后遇到任何“在有序数据中找边界”的问题你都能条件反射地写出二分。8. 收尾这道题值得多花点时间最后分享一点我在做这道题时的体会。这道题我前前后后写过不下五遍每次隔一段时间重写还是会犯一些小错误。后来我总结出原因二分查找的模板并不难背难的是每次都能想明白区间收缩的“为什么”。我个人的建议是不要急着背代码而是拿一张纸手动模拟一遍[1, 3, 5, 6]中查找 target 2 的过程每一步都写下 left、right、mid 的值以及为什么更新 left 或 right。手动模拟两三次之后你对边界条件的理解会有一个质变。如果你能把这道题的左闭右闭和左闭右开两种写法都理解透彻并且能独立推导出“查找第一个大于 target”和“查找最后一个小于等于 target”的代码那么二分查找这一关你就真正迈过去了。后续再遇到任何二分变体你都不会再慌。