Hello 算法二分查找左右边界binary_search_edge详解——重复有序数组中定位 target 首尾索引【免费下载链接】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 算法》检索章中「二分查找边界」一节为核心讲解如何在包含重复元素的有序数组中以 O(log n) 时间定位某个值target的最左出现位置与最右出现位置。你将掌握「复用插入点查找」与「转换为元素查找」两种优雅解法并通过仓库内 Python、Go、C、C、Rust 等十余种语言的源码印证实现细节可直接迁移到实际工程与面试手写场景。问题背景从普通二分到边界二分常规二分查找解决的是「有序无重复数组中是否存在target」返回值是下标m本身。但真实数据常常含有重复值例如仓库测试用例中反复使用的数组nums [1, 3, 6, 6, 6, 6, 6, 10, 12, 15]当target 6时6同时出现在下标 26。此时我们关心的不再是是否存在 6而是左边界最左侧的6位于哪个下标答案2右边界最右侧的6位于哪个下标答案6若数组中不存在该元素例如target 7两个函数都应返回-1。这正是 binary_search_edge.py 等文件所实现的binary_search_left_edge与binary_search_right_edge要解决的问题。复用基础带重复元素的插入点查找边界查找之所以代码极短关键在于它与「插入点查找」存在深刻关联。请回顾仓库中的 binary_search_insertion.py 所实现的binary_search_insertion它在有序数组中返回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请注意else分支即nums[m] target时向左收缩j m - 1循环结束后指针i恰好落在第一个不小于target的元素上。若数组中存在targeti就是最左的target若不存在i就是大于target的第一个元素下标。这便是整篇文章的核心思想插入点查找本质上就是最左target的查找。该函数与边界函数分离成独立文件模块例如 Rust 版通过mod binary_search_insertion;引入复用见 binary_search_edge.rsC 语言版则在同文件内静态实现并接收数组长度参数numSize见 binary_search_edge.c。查找左边界插入点 两次越界兜底左侧边界的实现思路是在插入点结果之上做校验。循环结束时可能有两种未找到的情形插入点下标i越出数组右边界i len(nums)说明所有元素都小于target自然不存在target插入点下标合法但nums[i] ! target说明插入点位置上是更大的元素target同样不存在。只要命中上述任一情形便返回-1否则i即为最左target的下标。以 Python 为例见 binary_search_edge.pydef binary_search_left_edge(nums: list[int], target: int) - int: 二分查找最左一个 target # 等价于查找 target 的插入点 i binary_search_insertion(nums, target) # 未找到 target 返回 -1 if i len(nums) or nums[i] ! target: return -1 # 找到 target 返回索引 i return iGo 语言版本的签名与逻辑完全对应只是将len(nums)替换为同样的切片长度调用并以func binarySearchLeftEdge(nums []int, target int) int形式呈现见 binary_search_edge.go。C 与 C 版本则把越界判断写成i numSize与i nums.size()见 binary_search_edge.c、binary_search_edge.cpp用于区分数组容量与内容。对于nums [1, 3, 6, 6, 6, 6, 6, 10, 12, 15]binary_search_left_edge(nums, 6)插入点返回 2nums[2] 6返回2binary_search_left_edge(nums, 7)插入点返回 710的位置但nums[7] ! 7返回-1。查找右边界三种思路的比较寻找最右target有几种方案第一种最直接把nums[m] target时的收缩方向改成向右扩张i m 1让循环自然滑向重复区间的右端。改动虽小但需要额外维护一套二分逻辑。本节介绍更优雅的两种复用型做法。思路一直接改写相等分支朴素法对普通二分做最小改动当nums[m] target时不急于返回而是令i m 1继续向右搜索。循环结束后j恰好停留在最右一个target上。该法逻辑直观但需要单独编写并维护一套与左边界对称的收缩逻辑代码有重复。思路二复用左边界查找把target 1当左边界找这是仓库源码实际采用的做法核心洞察是在整数数组中最右一个target的紧邻后继恰好是最左一个target 1的前一个位置。搜索结束后指针i指向最左的target 1若存在而指针j恰好压在最后一个target上因此直接返回j i - 1即可原理示意如下。对应的 Python 实现依然极其简短见 binary_search_edge.pydef binary_search_right_edge(nums: list[int], target: int) - int: 二分查找最右一个 target # 转化为查找最左一个 target 1 i binary_search_insertion(nums, target 1) # j 指向最右一个 target i 指向首个大于 target 的元素 j i - 1 # 未找到 target 返回 -1 if j -1 or nums[j] ! target: return -1 # 找到 target 返回索引 j return j这里仍需处理两种未找到的情形一是j -1即插入点为 0target 1比所有元素都小二是nums[j] ! target。注意i的越界情形由j i - 1的取法天然规避——target 1的插入点即使越界到len(nums)j也只会落到len(nums) - 1仍在合法下标内因此无需再检查i是否越界。仍以nums [1, 3, 6, 6, 6, 6, 6, 10, 12, 15]验证binary_search_right_edge(nums, 6)对target 7求插入点得i 7j 6且nums[6] 6返回6binary_search_right_edge(nums, 7)对target 8求插入点得i 7j 6但nums[6] ! 7返回-1。思路三转化为查找元素借助 ±0.5 消除歧义若数组中不存在target则二分结束后指针i会指向第一个大于target的元素指针j会指向最右一个小于target的元素。基于这一规律可以构造一个数组中必定不存在的元素来复用最普通的二分查找查最左target转为查找target - 0.5返回指针i查最右target转为查找target 0.5返回指针j。该法有两个注意点题目约定数组只含整数、不含小数所以target ± 0.5永远不会与任何数组元素相等规避了相等分支如何收缩的歧义可直接套用最朴素的二分查找模板由于引入了小数需要把函数中target参数的类型改为浮点型Python 因动态类型天然无需修改其余静态类型语言均需相应调整函数签名。该思路直观漂亮仓库文档指出其完整代码已省略可作为读者自行练习而官方实现最终选择了思路二的复用方案。多语言实现与运行验证本仓库将上述两函数在全部支持语言中保持了逻辑一致的同构实现可通过直接运行各语言的驱动代码driver code验证输出。例如 Python 版直接执行python3 codes/python/chapter_searching/binary_search_edge.py预期输出由 binary_search_edge.py 底部Driver Code段可推得数组 nums [1, 3, 6, 6, 6, 6, 6, 10, 12, 15] 最左一个元素 6 的索引为 2 最右一个元素 6 的索引为 6 最左一个元素 7 的索引为 -1 最右一个元素 7 的索引为 -1各语言实现的对应源文件均位于codes/lang/chapter_searching/目录包括Pythonbinary_search_edge.pyGobinary_search_edge.goCbinary_search_edge.c通过numSize参数显式传数组长度Cbinary_search_edge.cppRustbinary_search_edge.rs通过use binary_search_insertion::binary_search_insertion跨模块复用插入点函数复杂度与正确性分析时间复杂度 O(log n)无论是复用插入点查找还是执行target ± 0.5的元素查找每次迭代都把搜索区间缩小一半循环次数均为 O(log n)左/右边界函数至多额外执行常数次判断不改变量级。空间复杂度 O(1)全部实现均为迭代式while i j仅使用i、j、m等几个指针变量不依赖递归调用栈。从正确性角度两函数可以相互验证对同一数组与target左边界应满足left right且区间[left, right]内的所有元素都等于target。仓库文档中给出的全部代码均可直接运行自检适合作为「边界条件 指针不变量」的面试训练题。延伸阅读本文依赖的插入点查找原理解析binary_search_insertion.md基础二分查找与区间定义binary_search.md检索章节的总结与课后练习含左右边界综合应用summary.md、exercises.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），仅供参考