二分查找求插入位置详解：含重复元素时，怎么一步拿到最左下标

【免费下载链接】cleave.jsFormat input text content when you are typing...项目地址: https://gitcode.com/gh_mirrors/cl/cleave.js

普通二分查找只回答"查没查到"，而《Hello 算法》（hello-algo）仓库里的binary_search_insertion回答的是更有用的问题：把一个 target 插进有序数组，它该落在哪个下标。哪怕 target 已经躺在数组里，也要给出"插在它左侧"的那个位置。下面我们把含重复元素的版本放在最前面讲，先看最难的那一行改动，再回头证明它为什么成立。

为什么二分查找返回 -1 不够用

设想一套打卡系统：每位用户的历史打卡记录按时间戳升序存着，来一条新记录就得立刻确定它的"第几次"。

普通二分查找在这里会撞墙：

• 新时间戳不在旧记录里，程序返回 -1——可我们真正要的正是"该插在第几个"；
• 就算查到了，返回的还是"某个命中点"，重复记录扎堆时无法保证拿到最左边那个。

所以插入位置问题把返回值从"下标或 -1"换成了一个永远有效的下标：target 已存在，返回最左那个副本的下标；不存在，返回第一个比它大的下标。

含重复时只改这一行：命中也继续向左划界

👉 和普通二分相比，整段代码只动一处：命中分支从return m改成j = m - 1。

def binary_search_insertion(nums: list[int], target: int) -> int: """二分法求插入位置（数组可能含重复元素，返回最左插入下标）""" i, j = 0, len(nums) - 1 # 双闭区间 [i, j]，即"答案还可能在的范围" while i <= j: m = (i + j) // 2 # 中点 m（双闭区间的中点） if nums[m] < target: i = m + 1 # m 太靠左：答案只可能在 m 右边，区间收缩为 [m+1, j] else: # nums[m] >= target，含命中的情况 j = m - 1 # 关键改动：命中也不返回，把答案域收缩到 [i, m-1] return i # 区间收空时，i 恰好压在最左 target（或首个更大元素）上

先把改动钉死：nums[m] == target时不再停手，而是认为"最左的 target 只可能在 m 的左边或 m 自己"，于是把右边界收到m - 1。循环跑完，i停在哪里，答案就在哪里。

逐轮走查：区间如何一步步收缩到答案

拿nums = [1, 3, 4, 4, 4, 7, 10, 11, 15, 15, 20, 23]、target = 4（最左的 4 在下标 2）手算一遍：

循环结束时返回i = 2，正是最左那个 4 的下标。注意第 2 轮：命中了也没有停，区间照样砍掉右半——这是整个算法的全部秘密。

答案域收缩：循环结束时 i 为什么恰好是答案

换个视角看这个循环：它不是在"找 m 等不等于 target"，而是每一轮都在给答案划界。我们始终认定一个事实——

答案（最左插入下标）永远落在[i, j + 1]这个闭区间里，且循环每走一轮，这个区间至少减半。

• nums[m] < target：下标 0..m 处的值全都小于 target，插入点不可能落在它们身上，答案域收缩到[m+1, j+1]；
• nums[m] >= target：m 本身可能就是答案（值相等时它恰好是候选的最左 target），答案域收缩到[i, m]。

循环在i > j时停下，意味着答案域收缩成了单点{i}。此时可以反推两个边界：所有下标k < i的位置，值都必然小于 target（否则 i 早就被推得更远）；而nums[i]要么等于 target（i 就是最左 target），要么它是第一个大于 target 的元素（target 不存在，插在它前面）。两种情形下，i都是题目要的那个下标——不需要任何额外判断。

顺带一提：i和j恰好构成一对"分界线"——j停在"小于 target 的最右元素"上，i紧挨着它，指向"第一个不小于 target 的元素"。答案域收缩到零宽时，这条分界线正好穿过插入缝。

无重复元素版：return m 就是提前划定的边界

如果题目保证数组无重复，命中时m就是全部 target 中唯一的下标，它天然是"最左"，此时可以立刻返回：

def binary_search_insertion_simple(nums: list[int], target: int) -> int: """二分法求插入位置（数组不含重复元素）""" i, j = 0, len(nums) - 1 # 双闭区间 [i, j] while i <= j: m = (i + j) // 2 # 中点 m if nums[m] < target: i = m + 1 # 答案在 [m+1, j] elif nums[m] > target: j = m - 1 # 答案在 [i, m-1] else: return m # 无重复时，m 即最左 target，直接交卷 return i # 未命中：i 指向第一个大于 target 的元素

注意这里return m与上一节的j = m - 1是等价的：无重复时继续收缩到区间收空，i最终也会停到同一个m上；提前返回只是把"已确定的收缩结果"直接兑现，省掉几轮空转。

验证与边界：四类用例一次跑通

还是用nums = [1, 3, 4, 4, 4, 7, 10, 11, 15, 15, 20, 23]，把四类边界一次覆盖：

两版算法的时间都是 O(log n)、空间 O(1)——全程只用了i、j、m三个变量。

工程细节：防溢出中点与区间写法改写

• 中点防溢出：n 很大时i + j可能越过 32 位整数上限，仓库中 C 与 Java 实现统一写成i + (j - i) / 2；Python 无溢出问题，但保持同款写法没有坏处。
• 区间写法：上面两版都是双闭区间（含两端的[i, j]，即"答案还在 i 到 j 之间"），终止条件是i > j。把它改写成左闭右开[i, j)、条件换成i < j是个不错的练习——注意收缩规则与"答案在[i, j+1]"的划界逻辑要跟着对齐，别只改条件不动身体。

资源导航：实现源码与边界查找章节

仓库里各语言都有同名实现，Python 版在 codes/python/chapter_searching/binary_search_insertion.py，C 见 codes/c/chapter_searching/binary_search_insertion.c，Java 见 codes/java/chapter_searching/binary_search_insertion.java，Go 见 codes/go/chapter_searching/binary_search_insertion.go，其余语言在codes/下对应子目录。文档入口是 docs/chapter_searching/binary_search_insertion.md；它和 docs/chapter_searching/binary_search_edge.md 是配套的两章——求最左 target 本质上就是"求插入位置 + 一次相等校验"，两篇连读刚好。

小练习：把"最左插入"改成"最右插入"（target 插到所有相同元素之后）。别急着写循环——用答案域划界想清楚该收缩哪一侧，你会发现改动比想象中还少。

【免费下载链接】cleave.jsFormat input text content when you are typing...项目地址: https://gitcode.com/gh_mirrors/cl/cleave.js