企业官网建设流程全解析

hello-algo 二值搜索插入点：从 Python Tutor 逐步可视化理解插入位置的查找（无重复与含重复两种场景）

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文围绕《Hello 算法》（hello-algo）仓库中俄语版教程的配套文件 binary_search_insertion.md 展开，该文件为「二值搜索插入点」一节提供了两条 Python Tutor 逐步执行链接。读完本文，你将掌握：如何在有序数组中用 O(log n) 的二值搜索定位target应插入的下标（若target已存在则插入其左侧），以及仓库中 Python 源码实现 与 俄语文档 对两种场景（无重复元素、含重复元素）的完整推导过程。

一、pythontutor 文档的定位与文件结构

ru/codes/pythontutor/chapter_searching/binary_search_insertion.md 是 hello-algo 多语言文档体系中「Python Tutor 可视化片段」的一部分：仓库中每个codes/pythontutor/<chapter>/<name>.md文件并不包含正文，而是存放一组https://pythontutor.com/render.html#...链接，供文档站点通过<!-- [file]{...}-[class]{}-[func]{...} -->标记逐段注入，实现代码的逐步执行动画（step-by-step visualization）。

该文件包含两条链接，分别对应源码中的两个函数：

链接参数（以 URL query 形式编码在render.html#之后）承载了可视化配置，从源码结构看这些参数可归纳为：

• code=...：URL 编码后的完整 Python 脚本（函数定义 +if __name__ == "__main__"驱动代码）；
• py=311：按 Python 3.11 解释器渲染；
• mode=display：显示模式（非教学练习模式）；
• cumulative=false：不累积显示变量历史；
• curInstr=5：初始执行到第 5 条指令，打开链接即可看到函数调用前的状态快照；
• heapPrimitives=nevernest：堆对象展开策略；
• origin=opt-frontend.js、rawInputLstJSON=[]、textReferences=false：渲染器与输入选项。

因此该文件的价值在于：把 源文件 中两个函数的可运行代码打包成可逐帧单步的可视化页面，帮助学习者观察i、j、m三个指针在每一轮循环中的移动轨迹。

二、问题定义：插入点二值搜索

给定长度为 $n$ 的升序有序数组nums与元素target，要求把target插入nums并保持顺序；若target已存在，则插入到它左侧。返回插入后target所占的下标。

问题分两个变体：

1. 无重复元素：nums中不存在相同值；
2. 含重复元素：nums中可能存在多个target，此时必须返回最左侧target的下标。

三、无重复元素场景：复用二值搜索的收敛性质

复用标准二值搜索代码只需回答两个问题：

问题 1：若数组包含target，插入下标是否等于该元素的下标？是的。因为target要插入到相等元素的左侧，即新的target占据旧target的位置，所以数组包含target时，插入下标就是该target的下标。

问题 2：若数组不包含target，哪个元素的下标是插入点？观察二值搜索过程：当nums[m] < target时，指针 $i$ 右移，逐渐逼近第一个大于等于target的元素；当nums[m] > target时，指针 $j$ 左移，逐渐逼近最后一个小于target的元素。因此循环结束后必有：$i$ 指向第一个大于target的元素，$j$ 指向最后一个小于target的元素，插入下标即为 $i$。

对应实现（无重复元素版本，代码与 pythontutor 文档中嵌入的脚本 完全一致）：

def binary_search_insertion_simple(nums: list[int], target: int) -> int: """Бинарный поиск точки вставки (без повторяющихся элементов)""" i, j = 0, len(nums) - 1 # Инициализировать двусторонне замкнутый интервал [0, n-1] while i <= j: m = (i + j) // 2 # Вычислить индекс середины m if nums[m] < target: i = m + 1 # target находится в интервале [m+1, j] elif nums[m] > target: j = m - 1 # target находится в интервале [i, m-1] else: return m # Найти target и вернуть точку вставки m # target не найден, вернуть точку вставки i return i

两个关键细节：

• nums[m] == target分支直接return m，这是与含重复版本最大的差异；
• 循环自然结束后返回i，覆盖「插入点在尾部」的情形（例如target大于所有元素时返回 $n$）。

四、含重复元素场景：让指针继续逼近最左target

当数组中存在多个target时，普通二值搜索命中其中任意一个即返回，无法区分其左右各有多少个target。而题目要求插入最左侧，所以真正的目标是最左侧target的下标。

朴素做法（O(n)）：先二值搜索得到任意一个target的下标 $k$，再从 $k$ 开始线性向左扫描，直到找到最左的target。该方法可用但存在线性扫描，当target大量重复时退化为 $O(n)$。

二值搜索扩展做法（O(log n)）：保持每轮「先算中点 $m$，再比较nums[m]与target」的框架不变，仅调整相等分支：

• nums[m] < target或nums[m] > target：target尚未定位，执行标准区间收缩，$i$、$j$ 向target逼近；
• nums[m] == target：小于target的元素一定落在 $[i, m-1]$，因此令j = m - 1继续收缩，让 $j$ 逼近最后一个小于target的元素。

循环结束后，$i$ 恰好指向最左侧的target，$j$ 指向最后一个小于target的元素，插入点即 $i$：

def binary_search_insertion(nums: list[int], target: int) -> int: """Бинарный поиск точки вставки (с повторяющимися элементами)""" i, j = 0, len(nums) - 1 # Инициализировать двусторонне замкнутый интервал [0, n-1] while i <= j: m = (i + j) // 2 # Вычислить индекс середины m if nums[m] < target: i = m + 1 # target находится в интервале [m+1, j] elif nums[m] > target: j = m - 1 # target находится в интервале [i, m-1] else: j = m - 1 # Самый правый элемент, меньший target, находится в интервале [i, m-1] # Вернуть точку вставки i return i

从源码结构看，nums[m] > target与nums[m] == target两个分支的动作相同（都是j = m - 1），因此可以合并为一个else: j = m - 1；但仓库保留了展开写法，如 俄语文档 所述，这样逻辑更清晰、更易读。

五、源码验证：驱动代码与预期输出

完整实现与测试入口位于 ru/codes/python/chapter_searching/binary_search_insertion.py，可直接运行：

if __name__ == "__main__": # Массив без повторяющихся элементов nums = [1, 3, 6, 8, 12, 15, 23, 26, 31, 35] for target in [6, 9]: index = binary_search_insertion_simple(nums, target) print(f"Индекс позиции вставки элемента {target} равен {index}") # Массив с повторяющимися элементами nums = [1, 3, 6, 6, 6, 6, 6, 10, 12, 15] for target in [2, 6, 20]: index = binary_search_insertion(nums, target) print(f"Индекс позиции вставки элемента {target} равен {index}")

按算法逻辑推演，可验证以下结果：

Python 特有实现细节：

• m = (i + j) // 2使用整数除法向下取整，保证m < j（当 $i < j$ 时），避免死循环；
• Python 整数无溢出问题，无需像 C/Java 那样写(i + j) / 2 + i / 2之类的防溢出技巧——这一点在仓库其他语言版本的注释中也有体现，而 Python 版本注释直接说明「Python 整数理论上可任意大，因此无需考虑大数溢出」。

六、区间风格与二值搜索的指针不变量

俄语文档 特别提示：本节代码采用**「双闭区间」**风格（i, j均指向有效元素，循环条件i <= j），读者可以自行练习改写为「左闭右开」风格（i, j = 0, len(nums)，循环条件i < j，此时j = m）。同目录的 二值搜索 pythontutor 文件 中恰好同时提供了两种风格的binary_search与binary_search_lcro，可作为改写参照。

从整体视角看，二值搜索的本质是为指针 $i$ 和 $j$预先设定搜索方向：目标可以是一个具体元素（如target本身），也可以是某个元素集合（如「所有小于target的元素」）。在反复对半的过程中，$i$、$j$ 不断逼近预设目标，最终要么成功命中，要么在越过边界后停下——此时 $i$（或 $j$）本身就编码了答案。插入点问题正是「目标为元素集合」的典型代表：$i$ 收敛到第一个不小于target的元素，$j$ 收敛到最后一个小于target的元素，二者之间的缝隙就是插入位置。

七、复杂度小结

想进一步验证上述行为，可以在本地执行python3 ru/codes/python/chapter_searching/binary_search_insertion.py，或打开 pythontutor 片段文件 中的两条链接逐帧观察指针变化；完整推导与 8 帧动画见 ru/docs/chapter_searching/binary_search_insertion.md，同目录的 binary_search.md、binary_search_edge.md 则覆盖基础查找与边界处理，可配合阅读。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo