Hello 算法日本語版二分查找拓展二分搜索插入位置 binary_search_insertion 的推导、双指针不变式与实现详解【免费下载链接】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二分查找不仅能回答“target是否存在于有序数组中”还能解决一类更常见的派生问题——在保持数组有序的前提下求出target的插入位置索引。本文以《Hello 算法》日文版 binary_search_insertion.md 为主线结合仓库中 Python、C、Go、Java 等语言的真实实现完整推导“无重复元素”与“含重复元素”两套算法并用双指针不变式解释为什么循环结束后指针i一定指向正确插入位置让读者既能看懂结论也能理解推理过程并直接复现代码。1. 问题定义从“查找元素”到“求插入位置”回顾前一章 二分查找二分探索其任务是在不含重复元素的升序数组中找到target的下标找不到则返回-1。而本文讨论的问题发生了变化给定长度为n、不含重复元素的升序数组nums与元素target。要求把target插入nums并保持有序若数组中已存在target则插入到它的左侧。求插入后target的下标。注意与标准二分查找的关键差异即使target已存在也要返回一个位置而不是“未找到”且这个位置被规定为已存在元素自身的下标。上图中target 6已存在于数组内因此插入位置是原6的下标2插入后数组变为[1, 3, 6, 6, 8, …]最左侧的6正好落在原位置。1.1 能否直接复用普通二分查找要复用上一节的二分查找代码需要回答两个问题问题一数组中包含target时插入位置是target的下标吗是。因为题目要求把新元素插到相等元素的左侧插入后新的target顶替了原target的位置所以返回原target的下标即可。问题二数组中不包含target时插入位置落在哪里需要借助二分查找的指针语义来分析见下文。2. 无重复元素版本指针不变式推导插入位置回顾二分循环当nums[m] target时执行i m 1说明指针i始终在向“不小于target的第一个元素”逼近对称地当nums[m] target时执行j m - 1说明指针j始终在向“不大于target的最后一个元素”逼近。因此循环自然终止i j时必有i指向第一个大于或无重复时等价于“不小于”target的元素j指向最后一个小于target的元素。这正是推导的核心数组不含target时插入位置就是i数组含target时普通二分会在nums[m] target分支直接返回m而这个m正是该元素自身下标同样等于问题要求的答案。参考实现见 binary_search_insertion.py 中的binary_search_insertion_simpledef 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实现要点全程使用双闭区间[0, n-1]循环条件为i j区间为空即i j时终止。若找到target直接返回m若循环结束后仍未找到则说明i恰好越过j停在第一个不小于target的位置return i即为插入下标。以驱动测试数据为例对数组[1, 3, 6, 8, 12, 15, 23, 26, 31, 35]target 6返回2命中元素自身下标target 9返回4应插入在8与12之间。完整可运行示例参见 Java 实现 与 C 实现。3. 含重复元素版本为什么朴素做法退化为 O(n)现实场景中数组往往包含重复元素题目条件放宽为“可能含重复”其余要求不变插入最左、保持有序。此时普通二分遇到的问题是nums[m] target时只能返回某一个target的下标无法知道该元素左边/右边还有多少个target也就无法保证“最左插入”。3.1 朴素方案二分 向左线性扫描一种直觉做法分两步对应 linear 思路图先用普通二分找到任意一个target的下标记为k从k开始向左逐个扫描找到最左的target后返回。该方案虽然正确却引入了线性扫描最坏时间代价退化为O(n)——当数组中相同target大量聚集时例如连续 5 个6效率远不如纯二分。3.2 纯二分改进命中后继续向左缩小区间正确做法是保持二分框架不变只修改命中分支。每一轮仍先计算中点m再按三种情况处理nums[m] target或nums[m] target尚未遇到任何target按普通二分缩小区间让指针i、j不断向target靠拢nums[m] target说明更小的元素乃至更靠左的target只可能出现在[i, m-1]中因此执行j m - 1让指针j向“小于target的元素”逼近。循环结束后i停在最左的targetj停在小于target的最右元素于是答案就是i。这一过程的可视化分步图解见文档中的 step1 至 step8。对比两版代码可以发现nums[m] target与nums[m] target两个分支的处理完全相同因此理论上可合并为if nums[m] target: j m - 1 else: i m 1。不过《Hello 算法》文档明确指出保留独立的判定分支会让逻辑更清晰、可读性更高故实现中保持三分支写法。参考实现见 binary_search_insertion.pydef 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对含重复元素的数组[1, 3, 6, 6, 6, 6, 6, 10, 12, 15]三种典型输入可以验证边界行为target语义返回下标2介于1与3之间数组不含该值16数组含多个6须返回最左6220大于所有元素应插到数组末尾9上述测试数据与输出逻辑可在 Python Driver、C 的 main 函数 及 Java 的 main 方法 中直接运行验证。4. 本质指针就是查找目标本身含重复版本与无重复版本在代码上只差一行命中分支从return m改为j m - 1但其背后的统一思想值得提炼二分查找本质上就是给指针i与j分别设定一个查找目标。目标既可以是一个具体元素如target也可以是一个元素范围如“小于target的元素”。在反复二分的过程中两个指针不断向各自预设的目标逼近最终要么找到答案要么在越过边界处停下。无重复版本中i的目标是“第一个 ≥target的元素”j的目标是“最后一个 ≤target的元素”二者相撞之处就是答案含重复版本中j的目标被进一步收紧为“严格小于target的元素”从而迫使i停留在最左target上。这一不变式视角让算法不再依赖记忆结论而是可以被现场推导出来。从时间与空间看两版算法都保持二分查找的O(log n) 时间 / O(1) 空间只使用常数个指针变量。5. 与“二分查找边界”的关系与进阶练习掌握了插入位置算法后可以顺势将它复用到 边界查找二分探索の境界 中求最左target的本质就是求target的插入位置。当插入下标i越界或nums[i] ! target时说明数组不含target据此即可实现“查找左边界”函数而“右边界”则可通过“最左的target 1减一”等技巧转化得到。这种“一个问题引出多个工具函数”的推导顺序正是本章chapter_searching 目录编排上承上启下的设计。进阶练习建议本文两版代码均采用双闭区间写法可自行将[0, n-1]、i j改写为左闭右开区间[0, n)、i j的形式体会边界条件的变化。观察发现循环中nums[m] target与nums[m] target处理一致后可尝试将两个分支合并思考合并写法是否会牺牲可读性。6. 仓库内的多语言实现速查除文档内嵌代码外binary_search_insertion在本仓库中日文版代码目录ja/codes/下有完整的多语言实现与可运行测试Pythonja/codes/python/chapter_searching/binary_search_insertion.pyCja/codes/c/chapter_searching/binary_search_insertion.cCja/codes/cpp/chapter_searching/binary_search_insertion.cppJavaja/codes/java/chapter_searching/binary_search_insertion.javaGoja/codes/go/chapter_searching/binary_search_insertion.goJavaScript / TypeScript / Swift / Rust / C# / Ruby / Kotlin / Dart 等同名文件位于ja/codes/javascript/chapter_searching/、ja/codes/typescript/chapter_searching/、ja/codes/swift/chapter_searching/等对应子目录仓库根目录codes/下还保留了多语言版本的等价源码。各语言实现中需要注意的是当n很大时i j可能超过int上限因此中点统一采用i (j - i) / 2的安全写法C 与 Java 实现中均有体现例如 C 实现第 13 行。读者可将上述 Python 驱动逻辑移植到任意语言用 6.1 小节给出的测试用例做边界验证即可确认实现正确性。【免费下载链接】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），仅供参考
Hello 算法（日本語版）二分查找拓展：二分搜索插入位置 binary_search_insertion 的推导、双指针不变式与实现详解
Hello 算法日本語版二分查找拓展二分搜索插入位置 binary_search_insertion 的推导、双指针不变式与实现详解【免费下载链接】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二分查找不仅能回答“target是否存在于有序数组中”还能解决一类更常见的派生问题——在保持数组有序的前提下求出target的插入位置索引。本文以《Hello 算法》日文版 binary_search_insertion.md 为主线结合仓库中 Python、C、Go、Java 等语言的真实实现完整推导“无重复元素”与“含重复元素”两套算法并用双指针不变式解释为什么循环结束后指针i一定指向正确插入位置让读者既能看懂结论也能理解推理过程并直接复现代码。1. 问题定义从“查找元素”到“求插入位置”回顾前一章 二分查找二分探索其任务是在不含重复元素的升序数组中找到target的下标找不到则返回-1。而本文讨论的问题发生了变化给定长度为n、不含重复元素的升序数组nums与元素target。要求把target插入nums并保持有序若数组中已存在target则插入到它的左侧。求插入后target的下标。注意与标准二分查找的关键差异即使target已存在也要返回一个位置而不是“未找到”且这个位置被规定为已存在元素自身的下标。上图中target 6已存在于数组内因此插入位置是原6的下标2插入后数组变为[1, 3, 6, 6, 8, …]最左侧的6正好落在原位置。1.1 能否直接复用普通二分查找要复用上一节的二分查找代码需要回答两个问题问题一数组中包含target时插入位置是target的下标吗是。因为题目要求把新元素插到相等元素的左侧插入后新的target顶替了原target的位置所以返回原target的下标即可。问题二数组中不包含target时插入位置落在哪里需要借助二分查找的指针语义来分析见下文。2. 无重复元素版本指针不变式推导插入位置回顾二分循环当nums[m] target时执行i m 1说明指针i始终在向“不小于target的第一个元素”逼近对称地当nums[m] target时执行j m - 1说明指针j始终在向“不大于target的最后一个元素”逼近。因此循环自然终止i j时必有i指向第一个大于或无重复时等价于“不小于”target的元素j指向最后一个小于target的元素。这正是推导的核心数组不含target时插入位置就是i数组含target时普通二分会在nums[m] target分支直接返回m而这个m正是该元素自身下标同样等于问题要求的答案。参考实现见 binary_search_insertion.py 中的binary_search_insertion_simpledef 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实现要点全程使用双闭区间[0, n-1]循环条件为i j区间为空即i j时终止。若找到target直接返回m若循环结束后仍未找到则说明i恰好越过j停在第一个不小于target的位置return i即为插入下标。以驱动测试数据为例对数组[1, 3, 6, 8, 12, 15, 23, 26, 31, 35]target 6返回2命中元素自身下标target 9返回4应插入在8与12之间。完整可运行示例参见 Java 实现 与 C 实现。3. 含重复元素版本为什么朴素做法退化为 O(n)现实场景中数组往往包含重复元素题目条件放宽为“可能含重复”其余要求不变插入最左、保持有序。此时普通二分遇到的问题是nums[m] target时只能返回某一个target的下标无法知道该元素左边/右边还有多少个target也就无法保证“最左插入”。3.1 朴素方案二分 向左线性扫描一种直觉做法分两步对应 linear 思路图先用普通二分找到任意一个target的下标记为k从k开始向左逐个扫描找到最左的target后返回。该方案虽然正确却引入了线性扫描最坏时间代价退化为O(n)——当数组中相同target大量聚集时例如连续 5 个6效率远不如纯二分。3.2 纯二分改进命中后继续向左缩小区间正确做法是保持二分框架不变只修改命中分支。每一轮仍先计算中点m再按三种情况处理nums[m] target或nums[m] target尚未遇到任何target按普通二分缩小区间让指针i、j不断向target靠拢nums[m] target说明更小的元素乃至更靠左的target只可能出现在[i, m-1]中因此执行j m - 1让指针j向“小于target的元素”逼近。循环结束后i停在最左的targetj停在小于target的最右元素于是答案就是i。这一过程的可视化分步图解见文档中的 step1 至 step8。对比两版代码可以发现nums[m] target与nums[m] target两个分支的处理完全相同因此理论上可合并为if nums[m] target: j m - 1 else: i m 1。不过《Hello 算法》文档明确指出保留独立的判定分支会让逻辑更清晰、可读性更高故实现中保持三分支写法。参考实现见 binary_search_insertion.pydef 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对含重复元素的数组[1, 3, 6, 6, 6, 6, 6, 10, 12, 15]三种典型输入可以验证边界行为target语义返回下标2介于1与3之间数组不含该值16数组含多个6须返回最左6220大于所有元素应插到数组末尾9上述测试数据与输出逻辑可在 Python Driver、C 的 main 函数 及 Java 的 main 方法 中直接运行验证。4. 本质指针就是查找目标本身含重复版本与无重复版本在代码上只差一行命中分支从return m改为j m - 1但其背后的统一思想值得提炼二分查找本质上就是给指针i与j分别设定一个查找目标。目标既可以是一个具体元素如target也可以是一个元素范围如“小于target的元素”。在反复二分的过程中两个指针不断向各自预设的目标逼近最终要么找到答案要么在越过边界处停下。无重复版本中i的目标是“第一个 ≥target的元素”j的目标是“最后一个 ≤target的元素”二者相撞之处就是答案含重复版本中j的目标被进一步收紧为“严格小于target的元素”从而迫使i停留在最左target上。这一不变式视角让算法不再依赖记忆结论而是可以被现场推导出来。从时间与空间看两版算法都保持二分查找的O(log n) 时间 / O(1) 空间只使用常数个指针变量。5. 与“二分查找边界”的关系与进阶练习掌握了插入位置算法后可以顺势将它复用到 边界查找二分探索の境界 中求最左target的本质就是求target的插入位置。当插入下标i越界或nums[i] ! target时说明数组不含target据此即可实现“查找左边界”函数而“右边界”则可通过“最左的target 1减一”等技巧转化得到。这种“一个问题引出多个工具函数”的推导顺序正是本章chapter_searching 目录编排上承上启下的设计。进阶练习建议本文两版代码均采用双闭区间写法可自行将[0, n-1]、i j改写为左闭右开区间[0, n)、i j的形式体会边界条件的变化。观察发现循环中nums[m] target与nums[m] target处理一致后可尝试将两个分支合并思考合并写法是否会牺牲可读性。6. 仓库内的多语言实现速查除文档内嵌代码外binary_search_insertion在本仓库中日文版代码目录ja/codes/下有完整的多语言实现与可运行测试Pythonja/codes/python/chapter_searching/binary_search_insertion.pyCja/codes/c/chapter_searching/binary_search_insertion.cCja/codes/cpp/chapter_searching/binary_search_insertion.cppJavaja/codes/java/chapter_searching/binary_search_insertion.javaGoja/codes/go/chapter_searching/binary_search_insertion.goJavaScript / TypeScript / Swift / Rust / C# / Ruby / Kotlin / Dart 等同名文件位于ja/codes/javascript/chapter_searching/、ja/codes/typescript/chapter_searching/、ja/codes/swift/chapter_searching/等对应子目录仓库根目录codes/下还保留了多语言版本的等价源码。各语言实现中需要注意的是当n很大时i j可能超过int上限因此中点统一采用i (j - i) / 2的安全写法C 与 Java 实现中均有体现例如 C 实现第 13 行。读者可将上述 Python 驱动逻辑移植到任意语言用 6.1 小节给出的测试用例做边界验证即可确认实现正确性。【免费下载链接】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），仅供参考
