Hello 算法：二分查找左右边界（binary_search_edge）详解——重复有序数组中定位 target 首尾索引

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同时出现在下标 2～6。此时我们关心的不再是"是否存在 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 在区间 [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

请注意else分支（即nums[m] == target时）向左收缩j = m - 1，循环结束后指针i恰好落在第一个不小于target的元素上。若数组中存在target，i就是最左的target；若不存在，i就是大于target的第一个元素下标。这便是整篇文章的核心思想：插入点查找本质上就是最左target的查找。该函数与边界函数分离成独立文件模块，例如 Rust 版通过mod binary_search_insertion;引入复用（见 binary_search_edge.rs），C 语言版则在同文件内静态实现并接收数组长度参数numSize（见 binary_search_edge.c）。

查找左边界：插入点 + 两次越界兜底

左侧边界的实现思路是在插入点结果之上做校验。循环结束时可能有两种"未找到"的情形：

1. 插入点下标i越出数组右边界（i == len(nums)），说明所有元素都小于target，自然不存在target；
2. 插入点下标合法，但nums[i] != target，说明插入点位置上是更大的元素，target同样不存在。

只要命中上述任一情形便返回-1；否则i即为最左target的下标。以 Python 为例（见 binary_search_edge.py）：

def 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 i

Go 语言版本的签名与逻辑完全对应，只是将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)：插入点返回 2，nums[2] == 6，返回2；
• binary_search_left_edge(nums, 7)：插入点返回 7（10的位置），但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.py）：

def 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（即插入点为 0，target + 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 = 7，j = 6且nums[6] == 6，返回6；
• binary_search_right_edge(nums, 7)：对target = 8求插入点得i = 7，j = 6但nums[6] != 7，返回-1。

思路三：转化为"查找元素"，借助 ±0.5 消除歧义

若数组中不存在target，则二分结束后指针i会指向第一个大于target的元素，指针j会指向最右一个小于target的元素。基于这一规律，可以构造一个数组中必定不存在的元素来复用最普通的二分查找：

• 查最左target：转为查找target - 0.5，返回指针i；
• 查最右target：转为查找target + 0.5，返回指针j。

该法有两个注意点：

1. 题目约定数组只含整数、不含小数，所以target ± 0.5永远不会与任何数组元素相等，规避了"相等分支如何收缩"的歧义，可直接套用最朴素的二分查找模板；
2. 由于引入了小数，需要把函数中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/目录，包括：

• Python：binary_search_edge.py
• Go：binary_search_edge.go
• C：binary_search_edge.c（通过numSize参数显式传数组长度）
• C++：binary_search_edge.cpp
• Rust：binary_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