Skip to main content

Chapter 29: Binary Search Algorithms

核心问题与阅读主线

本章导读8 个核心小节 · 附自检与总结

工程中面对有序区间查询,核心痛点往往不是判断“值在不在”,而是精准切出重复键的左右边界、合法插入点,以及避免非随机访问迭代器带来的隐性线性步进开销。本章围绕 std::binary_search、std::lower_bound、std::upper_bound、std::equal_range 与 std::partition_point,建立边界语义、比较器契约与容器选型规则。

全章共用代码样本(下文各节持续拆解)

贯穿材料核心代码

贯穿材料使用一份含重复值的升序价格表,在同一份数据上对比存在性、左边界、右边界、等价范围与插入点。

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};
int target = 101;

bool exists = std::binary_search(prices.begin(), prices.end(), target);
auto first = std::lower_bound(prices.begin(), prices.end(), target);
auto last = std::upper_bound(prices.begin(), prices.end(), target);
auto range = std::equal_range(prices.begin(), prices.end(), target);

std::cout << std::boolalpha << exists << '\n';
std::cout << (first - prices.begin()) << ' ' << (last - prices.begin()) << '\n';
std::cout << (range.first - prices.begin()) << ' ' << (range.second - prices.begin()) << '\n';
}

运行后 exists 为 true,target == 101 的等价元素占据半开区间 [2, 5):first 与 range.first 均指向下标 2,last 与 range.second 均指向下标 5。

关键事实

C++ 标准 [alg.binary.search] 将以下算法统一定义在“区间已相对比较表达式分区”的前提之上:仅保证比较次数为对数级,不保证非随机访问迭代器的步进次数为对数级(参见 C++ draft binary search algorithms 与 cppreference binary search operations)。

算法返回值判定条件(自定义 comp)贯穿示例(target = 101)典型用途
std::binary_searchbool存在元素满足 !comp(*it, val) && !comp(val, *it)true仅确认等价元素是否存在
std::lower_bound迭代器首个使 comp(*it, val) 为假的位置下标 2左边界、最早合法插入点
std::upper_bound迭代器首个使 comp(val, *it) 为真的位置下标 5右边界后一位置、稳定尾插点
std::equal_rangestd::pair<It, It>{lower_bound, upper_bound}[2, 5)一次取全等价范围或缺席插入点
std::partition_point迭代器首个使一元谓词 pred(*it) 为假的位置下标 2(p < 101)任意单调布尔分区的分界点

29.1 binary_search​

std::binary_search 将已分区区间与目标值压缩为 bool 结果,仅回答“等价元素是否存在”,不携带位置、重复数量、插入点或稳定边界。

结构体按单字段排序查找时,这一语义差异会直接暴露:下例中 by_price 只比较 price,忽略 venue。

#include <algorithm>
#include <string>
#include <vector>

struct Quote {
int price;
std::string venue;
};

int main() {
std::vector<Quote> quotes{{100, "A"}, {101, "B"}, {101, "C"}, {103, "D"}};

auto by_price = [](const Quote& lhs, const Quote& rhs) {
return lhs.price < rhs.price;
};

bool has_price_101 = std::binary_search(
quotes.begin(), quotes.end(), Quote{101, "X"}, by_price
);
}

has_price_101 为 true,仅说明区间存在 price == 101 的记录,与 venue 是否为 "X" 无关。排查业务代码时,应先看比较器抽取的排序键,再解释结果。

边界与误区

注意

排序等价 ≠ operator== 相等:std::binary_search 判定等价的条件是 x < target 与 target < x 同为假(即 !comp(x, target) && !comp(target, x))。只要比较器未纳入全部字段,其余字段不同的对象也会落入同一等价类。

标准库通常将 binary_search 直接实现在 lower_bound 之上:先找首个不小于 value 的位置,再校验双方是否互不小于。

template<class ForwardIt, class T, class Compare>
bool mini_binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp) {
first = std::lower_bound(first, last, value, comp);
return first != last && !comp(value, *first);
}

可见 binary_search 并不比 lower_bound 多出定位能力;只要后续逻辑需要下标、计数或插入点,直接调用 lower_bound 或 equal_range,可避免从 bool 反向重算位置的错误。

29.2 lower_bound​

std::lower_bound 返回首个不排在目标值之前的位置(默认比较下 *it < value 为假,自定义比较器下 comp(*it, value) 为假)。它同时充当两个角色:已存在等价元素的左边界,以及保持有序的最早合法插入点。

std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

auto first_101 = std::lower_bound(prices.begin(), prices.end(), 101);
auto insert_102 = std::lower_bound(prices.begin(), prices.end(), 102);

auto index_101 = first_101 - prices.begin(); // 2
auto index_102 = insert_102 - prices.begin(); // 5
  • 查找 101:下标 0、1 满足 price < 101(true),从下标 2 起切换为 false,故左边界在下标 2。
  • 查找 102:前五个元素均满足 price < 102,直到下标 5(103)才切换为 false,故将 102 插在下标 5 可保持升序。

只要工程查询能抽象为“前段满足比较条件、后段不满足”,lower_bound 就可直接替代手写二分:

  • 定位排名与阈值:查找第一个不低于目标分数或阈值的记录。
  • 时间线截断:定位第一个不早于指定时间戳的事件。
  • 资源分桶:匹配第一个容量不低于需求的桶。

关键事实

std::lower_bound(first, last, value, comp) 始终按 comp(*it, value)(区间元素在左、目标值在右)调用。若需异构查找(如在 std::vector<std::string> 中用 std::string_view 查询),比较器必须支持“左元素、右目标”的参数类型(或使用透明比较器 std::less<>);C++20 std::ranges::lower_bound 还支持传入 projection 直接提取字段,避免构造临时哑对象。

29.3 upper_bound​

std::upper_bound 返回首个排在目标值之后的位置(默认比较下 value < *it 为真,自定义比较器下 comp(value, *it) 为真)。在贯穿材料中,upper_bound(..., 101) 跳过全部等价的 101(101 < 101 为假),停在首个使 101 < 103 为真的下标 5。

算法自定义比较器判别式返回边界语义重复键插入顺序
std::lower_bound首个使 comp(*it, value) 为假等价区间左边界新元素插在已有等价元素之前
std::upper_bound首个使 comp(value, *it) 为真等价区间右边界后一位置新元素插在已有等价元素之后

组合两个边界可直接计算重复元素数量,或用于保持同键相对顺序的稳定尾插:

std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

auto first = std::lower_bound(prices.begin(), prices.end(), 101);
auto last = std::upper_bound(prices.begin(), prices.end(), 101);
auto count = last - first; // 3

prices.insert(std::upper_bound(prices.begin(), prices.end(), 101), 101);
// 结果仍然升序,新 101 位于原有 101 之后。

边界与误区

注意

last - first 仅对随机访问迭代器是常数时间;若区间为前向迭代器,用 std::distance(first, last) 计数仍需线性步进。此外,二分只优化定位阶段,向 std::vector 中间 insert 仍会搬移插入点后的元素并可能触发扩容。

29.4 equal_range​

std::equal_range 一次返回等价元素的半开区间 [first, second),其中 first 等价于 lower_bound,second 等价于 upper_bound。目标值存在时返回全部等价元素范围;缺席时两个迭代器相等,共同指向合法插入点。

std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

for (int key : {101, 102}) {
auto [first, last] = std::equal_range(prices.begin(), prices.end(), key);
auto begin_index = first - prices.begin();
auto end_index = last - prices.begin();
auto count = last - first;
}

贯穿材料中,101 返回 [2, 5)(共 3 个等价元素),102 返回 [5, 5)(缺席且应插在下标 5)。该模型可直接用于提取有序日志中的同秒记录、同价位订单或同用户事件。

边界与误区

注意

双向比较器一致性:std::equal_range 会同时调用 comp(*it, value) 与 comp(value, *it)。若建表排序与查询比较器不一致、异构比较器只重载了单向参数顺序,或比较器依赖会变化的外部状态,分区前提即被破坏,轻则范围错位或遗漏元素,重则触发调试断言失败。

对 std::map、std::set、std::multimap、std::multiset 等树形关联容器,应优先调用成员函数 equal_range 而非同名泛型算法(原因见 29.8 节)。

29.5 partition_point​

std::partition_point 将二分查找从“有序值比较”泛化为“单调一元谓词分区”:只要前半段全部满足 pred(*it)、后半段全部不满足,它就返回首个使 pred(*it) 为假的位置(C++11 引入,C++20 起支持 constexpr)。

在贯穿材料中,lower_bound(..., 101) 等价于以 price < 101 为谓词调用 partition_point:

std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

auto first_101 = std::partition_point(
prices.begin(), prices.end(),
[](int price) { return price < 101; }
);

即使数据整体并未按大小排序,只要相对某个谓词先全真后全假,分界点依然成立。下例中 {8, 2, 6, 4, 5, 3, 7, 1} 按奇偶分区,first_odd 精准指向 5:

std::vector<int> values{8, 2, 6, 4, 5, 3, 7, 1};

auto first_odd = std::partition_point(
values.begin(), values.end(),
[](int x) { return x % 2 == 0; }
);

核心判断

二分查找定位的不是“等于目标的中点”,而是布尔序列从 true 切换到 false 的唯一边界。有序区间只是最常复用的分区来源;反过来,仅按谓词分区而未按值排序的区间不能调用 lower_bound,因为后者固定依赖比较表达式 comp(*it, value)。

29.6 前提条件:已排序区间​

二分算法的真正前提是“区间已相对当前比较表达式分区”。若区间按同一 comp 升序排列,对任意目标值都会满足 comp(*it, value) 先真后假、comp(value, *it) 先假后真,契约才能闭合。下例中建表与查询均以 by_price 比较 price,结果有标准保证:

struct Quote {
int price;
int sequence;
};

std::vector<Quote> quotes{{100, 1}, {101, 2}, {101, 3}, {103, 4}};

auto by_price = [](const Quote& lhs, const Quote& rhs) {
return lhs.price < rhs.price;
};

auto range = std::equal_range(
quotes.begin(), quotes.end(), Quote{101, 0}, by_price
);

前提失效通常源于以下三类破坏,编译器往往不会报错:

  • 比较键错配:建表按 price 排序,查询却改按 sequence 比较,区间对查询表达式不再单调,返回值无标准语义保证。
  • 非严格弱序:比较器破坏严格弱序会导致同键元素分散、等价类不再连续,equal_range 的半开区间模型随之失效。
  • 排序后原地改键:std::set 通过迭代器将键暴露为 const 以守住有序不变量;而 std::vector 排序后若原地修改键字段,有序性会静默失效,调用方必须重排或重建索引。

排查顺序

  1. 核对规则:确认建表排序与本次查询使用同一个比较表达式。
  2. 还原布尔序列:将元素逐一代入查询表达式,验证结果是否呈“连续 true 后接连续 false”。
  3. 检查严格弱序:确认比较器满足严格弱序,且不依赖可变全局状态。
  4. 排查原地修改:确认顺序容器元素在排序后未修改参与比较的键字段。

29.7 lower_bound 底层实现​

lower_bound 的核心骨架围绕四个状态推进:候选起点 first、候选长度 count、步长 step 与中点 it。算法通过 std::distance 与 std::advance 支持前向迭代器:

#include <iterator>

template<class ForwardIt, class T, class Compare>
ForwardIt mini_lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp) {
using difference_type = typename std::iterator_traits<ForwardIt>::difference_type;

difference_type count = std::distance(first, last);

while (count > 0) {
ForwardIt it = first;
difference_type step = count / 2;
std::advance(it, step);

if (comp(*it, value)) {
first = ++it;
count -= step + 1;
} else {
count = step;
}
}

return first;
}

循环不变量始终是“最终边界位于当前半开区间 [first, first + count) 内”:

  • comp(*it, value) 为真:*it 及其左侧元素全部排在目标之前,必不是答案,故令 first = ++it 并减去左半段与中点(count -= step + 1)。
  • comp(*it, value) 为假:it 本身可能就是答案,仅丢弃右半段,收缩长度为 count = step。

在贯穿材料 {100, 100, 101, 101, 101, 103, 106} 上执行 lower_bound(..., 101) 的收缩过程如下:

轮次候选区间 [first, first + count)countstep中点 it 及元素comp(*it, 101)区间更新
1[0, 7)73下标 3(101)falsecount = 3 → [0, 3)
2[0, 3)31下标 1(100)truefirst = 2, count = 1 → [2, 3)
3[2, 3)10下标 2(101)falsecount = 0 → 返回下标 2

核心判断

lower_bound 找的是分界点,不要求中点命中等于目标的值;每轮 count 减半只把比较次数压到对数级,而构造中点时 std::advance(it, step) 的移动成本完全由底层迭代器类别决定。

29.8 iterator category 对复杂度的影响​

评估二分查找性能必须拆开两个维度:比较次数与迭代器步进 / 节点跳转次数。标准仅承诺比较次数为对数级,而不同容器到达中点的方式截然不同:

容器 / 区间类型迭代器类别调用方式比较次数步进 / 跳转成本工程结论
std::vector / std::deque / std::array随机访问std::lower_bound 等泛型算法对数级对数级(+ step 常数跳转)最典型适用场景,连续内存缓存友好
std::set / std::map 等关联容器双向成员函数 c.lower_bound(k) 等对数级对数级(沿树节点跳转)必须优先选用成员函数
std::set / std::map 误用泛型算法双向std::lower_bound(c.begin(), ...)对数级线性级(advance 逐节点步进)语义相同但丢失树结构跳转优势
std::list / std::forward_list双向 / 前向泛型算法(不推荐)对数级线性级(逐节点指针追踪)少比较无法抵消遍历成本,应换容器
#include <algorithm>
#include <set>
#include <vector>

int main() {
std::vector<int> v{1, 2, 4, 8, 16, 32};
std::set<int> s{1, 2, 4, 8, 16, 32};

auto a = std::lower_bound(v.begin(), v.end(), 8); // 适合随机访问区间
auto b = s.lower_bound(8); // 适合树形容器
}

核心判断

二分算法只优化“缩小候选区间时的比较次数”,迭代器能力才决定“到达中点”的真实开销:连续有序区间用泛型算法,树形关联容器用成员函数,链表类容器先重构数据结构;若场景需高频插入并维持有序,还应把顺序容器元素搬移与节点分配成本一并计入。

最小自检任务​

动手自检先独立判断

阅读下面代码,判断四个问题:

  1. has_101 的准确含义是什么?
  2. range_101 覆盖哪些下标?
  3. range_102 为什么是空区间?
  4. 将最后一行改为 std::lower_bound(s.begin(), s.end(), 101) 后,标准语义与工程成本分别有何变化?
#include <algorithm>
#include <set>
#include <vector>

int main() {
std::vector<int> prices{100, 100, 101, 101, 101, 103, 106};

bool has_101 = std::binary_search(prices.begin(), prices.end(), 101);
auto range_101 = std::equal_range(prices.begin(), prices.end(), 101);
auto range_102 = std::equal_range(prices.begin(), prices.end(), 102);

std::set<int> s{100, 101, 103, 106};
auto pos = s.lower_bound(101);
}

本章知识点总结​

  • 分区前提

    二分算法依赖区间对当前比较表达式呈单调布尔分区(先 true 后 false);排序与查询比较器错配、破坏严格弱序或原地修改键字段都会破坏契约。

  • 存在性与等价

    std::binary_search 仅返回 bool,等价由排序关系 !comp(x, val) && !comp(val, x) 而非 operator== 定义;需要位置或计数时应直接选用 lower_bound 或 equal_range。

  • 左右边界与插入点

    std::lower_bound 定位首个使 comp(*it, val) 为假的位置(左边界 / 最早插入点),std::upper_bound 定位首个使 comp(val, *it) 为真的位置(右边界后一位置 / 稳定尾插点)。

  • 等价范围与双向一致

    std::equal_range 一次返回 [lower_bound, upper_bound)(缺席时为 [pos, pos));因其同时调用 comp(*it, val) 与 comp(val, *it),自定义及异构比较器必须保证双向一致。

  • 谓词分界泛化

    std::partition_point 定位任意单调一元谓词从 true 切到 false 的位置,不要求区间按值有序,但仅按谓词分区的区间不能反推调用 lower_bound。

  • 骨架与隐性成本

    lower_bound 通过收缩 [first, first + count) 定位分界点,仅保证比较次数为对数级;非随机访问迭代器上的 std::advance 定位中点及 std::distance 计数均呈线性成本。

  • 容器与接口选型

    连续有序区间优先用泛型算法;std::set / std::map 等关联容器必须优先用成员函数 lower_bound / upper_bound / equal_range;链表类容器应先重审数据结构再谈二分。