简介

C++中有序序列的二分查找一般会有两种方法，一个叫lower_bound，另一个叫upper_bound

简单来说，这个命名很不直观

二分基本逻辑

众所周知，二分是对序列进行区间划分，以mid_element(seq)为中心，将seq分为左区间和右区间，判断目标点位于区间A中，使用区间A的元素作为新的seq，重复该过程，直到区间内元素数量为0，此时区间端点就有可能是目标点。

于是这里会产生一个问题，如何以某个点为中心将seq划分为两个区间：

[bg, mid) [mid, ed]

[bg, mid] (mid, ed]

显然有以上两种划分方式。我们最后希望让mid是我们的目标点，所以目标点会在包含mid的闭区间中：

[bg, mid) [mid, ed] 中的 [mid, ed] 这个区间的下端点（lower_bound）是目标点

[bg, mid] (mid, ed] 中的 [bg, mid] 这个区间的上端点（upper_bound）是目标点

这样便能够与C++接口对应起来了。

内容

C++约定，二分查找接口返回的永远是右区间的begin()（未找到情况下是end()）

在查找成功时，lower_bound返回的是“第一个>=目标点的区间左端点迭代器”（显然右区间包含目标点）

在查找成功时，upper_bound返回的是“第一个>目标点的区间左端点迭代器”（显然右区间不包含目标点）

总结

C++二分查找接口命名表示“目标点应该在上边界还是下边界”，间接描述了二分划分边界的方式。

无论如何划分区间，接口返回迭代器一定是右区间的下边界（可能为end）。