二分搜索边界变体：左边界右边界

可视化演示

二分搜索的边界变体包括查找左边界和右边界，用于在有序数组中找到目标值的首次和末次出现位置。本文讲解左边界查找的... 切换模式查看不同维度。

标准二分基础

引座员第一次拿起手电筒，最聪明的策略不是从 0 号座位挨个照，而是先照正中间。如果中间那位观众说自己是 2 号、比 3 号小，那么他左边所有的座位都不可能是 3 号了——因为这一排座位号从左到右递增。一次照射排除一半，这就是二分搜索的原型。它有一个大前提：座位号必须有序，否则“中间比目标小”根本推不出“左边全都小”。

在算法术语里，“这一排座位”叫有序数组，座位编号叫下标，要找的票号叫目标值 target。每次取当前区间 [L, R] 的中点 mid，比较 arr[mid] 与 target：中间值太小就舍弃左半边，太大就舍弃右半边。区间每轮缩小一半，n 个元素最多查 log₂n 次，这就是对数时间复杂度的由来。整个过程的循环不变量是：“只要 target 存在，它就一定还在当前 [L, R] 区间里”——每次收缩都必须守住这句话，手电筒才不会照丢人。

$$\displaystyle \text{mid} = L + \left\lfloor \frac{R - L}{2} \right\rfloor$$

1. 计算区间跨度：用 R - L 求出当前待查区间的间隔数，比如 L=0、R=9 时跨度是 9。

$$R - L$$

2. 跨度折半：把跨度除以 2，得到区间一半的长度，这是“折半”思想的数学表达。

$$\frac{R - L}{2}$$

3. 向下取整：用 floor 抹掉小数，保证 mid 是合法的整数下标。

$$\left\lfloor \frac{R - L}{2} \right\rfloor$$

4. 偏移回中点：把相对偏移加回左端点 L，变成数组里真实的中间位置下标。

$$\text{mid} = L + \left\lfloor \frac{R - L}{2} \right\rfloor$$

手电筒一次照亮一半，这就是标准二分。但它只能回答“有没有”这个是非题，回答不了“第一个在哪儿、最后一个在哪儿”。于是引座员必须学会两种更精细的照法：一种向左追，一种向右追。

左边界查找

引座员的新任务是找到最左边的 3 号。他照到中间座位，发现是 3 号，但他不敢停——左边可能还坐着别的 3 号。于是他把照射范围的右端收回到 mid 的左侧（R = mid - 1），继续向左追。每一次照到 3 号都往左收一次，直到光圈彻底空掉。这个过程就是“左边界查找”，也叫 lower_bound。

规则只有一句话：只要 arr[mid] >= target，就把右边界收缩到 mid - 1；否则（arr[mid] < target）把左边界收缩到 mid + 1。注意“等于也要向左收”，这正是它与标准二分最大的区别——标准二分见到相等就 return，而左边界查找见到相等反而要逼自己往左看，因为左边可能存在更靠前的目标。收缩过程中，循环不变量依然是“第一个目标一定在当前区间内”，只是现在的判断标准从“有没有”变成了“第一个在哪”。

$$\displaystyle \text{while } L \le R: \quad \text{if } arr[mid] \ge t,\ R = mid - 1;\ \text{else } L = mid + 1;\ \text{返回 } L$$

1. 循环条件：L <= R 表示手电筒光圈里还有候选座位，就继续照。

$$L \le R$$

2. 取中点：和标准二分一样求 mid，这是每次照射的落点。

$$\text{mid} = L + \left\lfloor \frac{R - L}{2} \right\rfloor$$

3. 相等或偏大向左收：arr[mid] >= t，说明第一个 t 不可能在 mid 右边，把右端收到 mid 左侧。

$$R = mid - 1$$

4. 偏小向右收：arr[mid] < t，说明目标只可能在右边，把左端收到 mid 右侧。

$$L = mid + 1$$

5. 返回左指针：退出时 L 正是第一个 >= t 的位置，即左边界。

$$\text{返回 } L$$

演示图中上排完整走了一遍这个过程：arr[mid]=3 时不返回，而是 R=3、再 R=1，最终 L=2 停在第一个 3 号面前。引座员总结出一条经验：找“第一个”，就要做到“见到目标也贪心，继续把右端往左赶”。

右边界查找

现在任务反过来：找最右边的 3 号。引座员把规则镜像翻转——照到 3 号，不往左收，而是把左端收到 mid 右侧（L = mid + 1），继续向右追；只有照到大于 3 号的座位，才把右端收回来。这套对称的追法就是“右边界查找”，也叫 upper_bound。

对称体现在方方面面：左边界“等值收缩右端”，右边界“等值收缩左端”；左边界返回 L，右边界返回 R。具体规则是：arr[mid] <= target 时 L = mid + 1；arr[mid] > target 时 R = mid - 1。循环退出时 R 停在最后一个 <= target 的位置，也就是 target 的末次出现位置（若 target 存在）。这里要先埋一个伏笔：如果为了代码好看而把收缩写成 L = mid 而不是 L = mid + 1，mid 就必须向上取整，否则区间只剩两个元素时会陷入死循环，我们留到“死循环防范”一节再拆解。

$$\displaystyle \text{while } L \le R: \quad \text{if } arr[mid] \le t,\ L = mid + 1;\ \text{else } R = mid - 1;\ \text{返回 } R$$

1. 相等或偏小向右收：arr[mid] <= t，说明最后一个 t 不可能在 mid 左边，把左端收到 mid 右侧。

$$L = mid + 1$$

2. 偏大向左收：arr[mid] > t，说明目标在左边，把右端收到 mid 左侧。

$$R = mid - 1$$

3. 返回右指针：退出时 R 恰好是最后一个 <= t 的位置，即右边界。

$$\text{返回 } R$$

回到演示图的下排：照到 3 号不满足，L 一路从 0 推到 7，最终 R=6 停在最后一个 3 号面前。引座员满意地点点头：左边界返回 L、右边界返回 R，两只指针之间夹着的，正是那七个连坐的 3 号观众。

区间写法对比

手电筒的光圈有两种标记法。第一种是“两端都照”：范围 [L, R] 左右端点都包含在候选里；第二种是“右端只照到门口”：[L, R) 左端包含、右端不包含。同样是找左边界，两种照法写出来的代码并不一样——这常常是初学者最容易搞混的地方。

左闭右闭（[L, R]）的写法是：while (L <= R)，收缩时 R = mid - 1、L = mid + 1。原因是 mid 已经被比较过，必须排除出候选。左闭右开（[L, R)）的写法是：while (L < R)，收缩时 R = mid、L = mid + 1。原因是 R 本身是开区间端点、不参与比较，收缩时直接把它拉到 mid 即可，不用再减一；退出时 L == R，这个位置就是答案。一句话记忆：闭区间“比较过的就排除”，开区间“右端本来就是排除区，收进来不用减一”。

$$\displaystyle \text{左闭右开: } \text{while } L < R: \quad \text{if } arr[mid] \ge t,\ R = mid;\ \text{else } L = mid + 1;\ \text{返回 } L$$

1. 开区间语义：[L, R) 中 R 是“已排除区间的起始点”，它本身不参与候选，只负责划定边界。

$$[L,\ R)$$

2. 退出条件不同：区间缩到只剩一个元素时 L == R，循环结束，答案就是 L。

$$L < R$$

3. 右端收缩：因为 R 不参与比较，收缩时把 R 拉到 mid 即可，不需要 mid - 1。

$$R = mid$$

4. 左端收缩：L 参与比较，收缩时必须排除 mid，所以是 mid + 1。

$$L = mid + 1$$

引座员恍然大悟：光圈“闭哪一端”决定了语法里的一切细节。只要想清楚“哪端包含、哪端排除”，无论左闭右闭还是左闭右开，都能稳稳找到第一个 3 号。真正重要的不是背模板，而是理解区间语义。

应用场景

引座员发现边界二分的用途远不止“找人”。有新人进场问“我该坐哪个空位”，这需要查找插入位置；经理问“这一排到底坐了几个三号观众”，这需要统计出现次数；还有观众问“3 号到 4 号之间坐了哪些人”，这需要范围查询。三个问题，同一支手电筒。

第一个场景是查找插入位置：在有序数组中插入新元素并保持有序，lower_bound(t) 返回的 L 就是新元素该放的下标，把原位置的元素整体右移即可。第二个场景是范围查询：想知道值落在 [a, b] 区间的所有元素，用 lower_bound(a) 得到起点，用 upper_bound(b) 得到终点，两个下标之间的连续切片就是答案。第三个场景是统计个数：count = upper_bound(t) - lower_bound(t) + 1；如果 lower 大于 upper，说明数组里根本没有 t，个数为 0。数据库索引的范围扫描、特征工程里的区间统计、日志按时间戳截取，全都在用这套逻辑。

$$\displaystyle \text{count} = \text{upper} - \text{lower} + 1, \qquad \text{若 } \text{lower} > \text{upper} \text{，则 } \text{count} = 0$$

1. 定位左界：lower = lower_bound(t) 返回第一个 >= t 的下标，作为区间起点。

$$\text{lower} = \text{lower\_bound}(t)$$

2. 定位右界：upper = upper_bound(t) 返回最后一个 <= t 的下标，作为区间终点。

$$\text{upper} = \text{upper\_bound}(t)$$

3. 计算长度：闭区间元素个数 = 终点 - 起点 + 1。

$$\text{count} = \text{upper} - \text{lower} + 1$$

4. 空集判定：当 lower > upper 时表示区间为空，个数记 0。

$$\text{count} = 0$$

引座员把台词默念一遍：找第一个、找最后一个、找插入位、数个数，全是同一支手电筒的四种用法。掌握一支手电筒，就等于同时掌握了四样本领。

死循环防范

手电筒最怕什么？怕每轮明明“动了”，光圈却根本没变小。传说中有位粗心的引座员，为了追求左右边界的代码对称，把收缩规则改成了 L = mid。结果遇到只剩两个候选座位时，mid 向下取整永远等于左端，光圈卡在两个座位之间来回横跳，电影散场了还没找到人。

死循环的根因就是“区间没有必然收缩”。在 while (L <= R) 的框架下，如果收缩规则允许 L 或 R 取到 mid，而当 R = L + 1、mid 向下取整时，mid = L，一旦走进 L = mid 的分支，左端纹丝不动，区间长度永远是 2，程序就永远转圈。防范办法有三：第一，优先写 L = mid + 1 / R = mid - 1，保证每轮至少排除一个元素；第二，如果非要写 L = mid，就必须让 mid 向上取整，即 mid = (L + R + 1) // 2；第三，在函数入口检查空数组和 target 越界，避免返回 -1 或 len(arr) 这类非法下标。最后别忘了用边界用例测试：空数组、全部相等、目标在两端、目标不存在，四个用例各跑一遍，代码才敢上线。

$$\displaystyle \text{mid} = L + \left\lceil \frac{R - L}{2} \right\rceil = L + \left\lfloor \frac{R - L + 1}{2} \right\rfloor$$

1. 陷阱现场：当区间只剩两个元素（R = L + 1）且收缩规则是 L = mid 时，向下取整会让 mid = L，左端永远不动。

$$R - L = 1$$

2. 向上取整：把折半方式改成 ceil，mid 会取到 R，区间必然向左收缩。

$$\text{mid} = L + \left\lceil \frac{R - L}{2} \right\rceil$$

3. 等价整数写法：ceil((R-L)/2) 等于 floor((R-L+1)/2)，便于用整除实现。

$$\left\lceil \frac{R - L}{2} \right\rceil = \left\lfloor \frac{R - L + 1}{2} \right\rfloor$$

引座员终于顿悟：二分查找的命门不是“聪明”，而是“每轮都必须缩小范围”。只要守住这条铁律，手电筒的每一次闪烁都离真相更近一步；守不住，再亮的灯也只能在原地打转。

AI 应用场景

Python 演示

def lower_bound(arr, target):    """返回第一个 >= target 的下标(左边界, 也为插入位置)"""    left, right = 0, len(arr) - 1    while left <= right:        mid = left + (right - left) // 2        if arr[mid] >= target:            right = mid - 1        else:            left = mid + 1    return left  def upper_bound(arr, target):    """返回最后一个 <= target 的下标(右边界)"""    left, right = 0, len(arr) - 1    while left <= right:        mid = left + (right - left) // 2        if arr[mid] <= target:            left = mid + 1        else:            right = mid - 1    return right  def count_in_range(arr, low, high):    """统计值落在闭区间 [low, high] 内的元素个数"""    if not arr:        return 0    lo = lower_bound(arr, low)    hi = upper_bound(arr, high)    return max(0, hi - lo + 1)  def main():    arr = [1, 2, 3, 3, 3, 3, 3, 4, 5, 6]    for t in [3, 0, 9]:        lb = lower_bound(arr, t)        ub = upper_bound(arr, t)        if lb <= ub and lb < len(arr) and arr[lb] == t:            print("target={}: count={}, range=[{},{}]".format(t, ub - lb + 1, lb, ub))        else:            print("target={}: not found, insert at {}".format(t, lb))    print("count in [3,4]:", count_in_range(arr, 3, 4))    print("count in [7,9]:", count_in_range(arr, 7, 9))    print("empty array lower_bound(1):", lower_bound([], 1))  if __name__ == "__main__":    main()

1. if arr[mid] >= target:左边界的关键判断：等值也不停，继续向左收。
2. right = mid - 1把右端收到 mid 左侧，排除已比较过的元素。
3. if arr[mid] <= target:右边界的关键判断：等值继续向右追。
4. left = mid + 1把左端推到 mid 右侧，保证区间每轮收缩。
5. mid = left + (right - left) // 2防溢出的中点写法，等价于 (left+right)//2 但更安全。
6. if lb <= ub and lb < len(arr) and arr[lb] == t:用边界关系判断 target 是否存在，比“返回 -1”语义更丰富。
7. max(0, hi - lo + 1)空区间保护，避免 lower 大于 upper 时算出负数。

常见误区

面试题