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。该文件包含两条链接分别对应源码中的两个函数标记注释对应函数场景[func]{binary_search_insertion_simple}binary_search_insertion_simple数组无重复元素[func]{binary_search_insertion}binary_search_insertion数组允许重复元素链接参数以 URL query 形式编码在render.html#之后承载了可视化配置从源码结构看这些参数可归纳为code...URL 编码后的完整 Python 脚本函数定义 if __name__ __main__驱动代码py311按 Python 3.11 解释器渲染modedisplay显示模式非教学练习模式cumulativefalse不累积显示变量历史curInstr5初始执行到第 5 条指令打开链接即可看到函数调用前的状态快照heapPrimitivesnevernest堆对象展开策略originopt-frontend.js、rawInputLstJSON[]、textReferencesfalse渲染器与输入选项。因此该文件的价值在于把 源文件 中两个函数的可运行代码打包成可逐帧单步的可视化页面帮助学习者观察i、j、m三个指针在每一轮循环中的移动轨迹。二、问题定义插入点二值搜索给定长度为 $n$ 的升序有序数组nums与元素target要求把target插入nums并保持顺序若target已存在则插入到它左侧。返回插入后target所占的下标。问题分两个变体无重复元素nums中不存在相同值含重复元素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 находится в интервале [m1, 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] targettarget尚未定位执行标准区间收缩$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 находится в интервале [m1, 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})按算法逻辑推演可验证以下结果数组target返回下标说明[1, 3, 6, 8, 12, 15, 23, 26, 31, 35]62命中已有元素插入其自身左侧即原位[1, 3, 6, 8, 12, 15, 23, 26, 31, 35]94不存在插入到第一个大于它的元素 12 处[1, 3, 6, 6, 6, 6, 6, 10, 12, 15]21不存在插入到第一个大于它的元素 6 处[1, 3, 6, 6, 6, 6, 6, 10, 12, 15]62返回最左侧的 6而非中间或右侧的 6[1, 3, 6, 6, 6, 6, 6, 10, 12, 15]2010大于所有元素插入到数组末尾之后越界下标 $n$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的元素二者之间的缝隙就是插入位置。七、复杂度小结版本时间复杂度空间复杂度适用输入朴素做法二值搜索 左向线性扫描$O(n)$最坏$O(1)$含重复元素binary_search_insertion_simple$O(\log n)$$O(1)$无重复元素binary_search_insertion$O(\log n)$$O(1)$含重复元素返回最左插入点想进一步验证上述行为可以在本地执行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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考