stl 中的二分查找¶

假设有一个**升序**序列。

• lower_bound(begin, end, val)： 返回第一个 大于或等于 val 的元素的迭代器。
• upper_bound(begin, end, val)： 返回第一个 大于 val 的元素的迭代器。
• lower 是“下界”，即 val 能够出现的 第一个 位置。
• upper 是“上界”，即 val 能够出现的 最后一个位置的后面一个 位置。

假设数组为 a = {10, 20, 30, 30, 30, 40, 50}。

情况 A：目标值 val 在序列中存在¶

查找 val = 30：

• lower_bound：指向第一个 30 的位置（索引 2）。
• upper_bound：指向第一个比 30 大的数，即 40 的位置（索引 5）。
• 用途：这两个迭代器构成的区间 [it1, it2) 正好是所有等于 30 的元素范围。

情况 B：目标值 val 不在序列中，但在范围内¶

查找 val = 25：

• lower_bound：指向 30 的位置（第一个 30，索引 2）。
• upper_bound：指向 30 的位置（第一个 30，索引 2）。
• 结论：当 val 不存在时，两者返回相同的迭代器，都指向“如果 val 存在，它应该被插入的位置”。

情况 C：目标值 val 比序列中所有元素都小¶

查找 val = 5：

• 两者都返回 begin()（索引 0）。

情况 D：目标值 val 比序列中所有元素都大 (找不到的情况)¶

查找 val = 60：

• 两者都返回 end()（即指向最后一个元素之后的位置）。
• 注意：end() 是不能直接解引用（*it）的，否则会导致崩溃。