关于std::lower_bound和std::upper_bound的技术问询：近似有序数据查找

先快速对齐下你的场景：你正在优化一个存储Level（含Price、Bid、Ask）的std::vector查找逻辑，其中Price严格递增，Bid整体升序、Ask整体降序，大部分元素的Bid/Ask是0或-1（无意义值），仅需搜索正值。现在有两个关于STL查找算法的疑问，咱们逐个拆解：

疑问1：是否需要把所有-1转为0才能保证查找正确？负数值会导致未定义行为吗？ #

首先明确两个关键点：

1. STL查找算法的核心要求是序列满足「严格弱序」，而非必须是全非负或某种特定数值范围。只要你提供的谓词符合严格弱序规则（即传递性、非自反性，等价元素的判断一致），就不会触发未定义行为。
2. 你的场景中，0和-1都是无意义值，本质上等价于「比所有正值小的无效元素」——因为你只搜索正值，所以这些无效值在查找逻辑里应该被统一视为“排在所有有效元素之前”的存在。

基于此，完全不需要把-1转为0。只要在谓词里正确区分无效值和有效值即可：比如搜索Bid≥目标值时，把所有Bid≤0的元素都视为“小于目标值”（因为目标是正值），这样std::lower_bound会自动跳过这些无效元素，找到第一个符合要求的有效元素。

举个谓词示例（针对Bid查找）：

auto it = std::lower_bound(levels.begin(), levels.end(), seek_bid,
    [](const Level& l, int target) {
        // 无效值直接视为小于目标
        if (l.Bid <= 0) return true;
        // 有效值正常比较
        return l.Bid < target;
    });

这里负数值（-1）只会被当作无效值处理，不会破坏严格弱序，因此不会产生未定义行为。

疑问2：为什么lambda谓词中用<而非<=才能得到正确结果？ #

这得从std::lower_bound和std::upper_bound的核心语义说起：

• std::lower_bound：返回第一个**不满足「元素 < 目标值」**的元素，也就是第一个≥目标值的元素（当序列升序时）。
• std::upper_bound：返回第一个**满足「目标值 < 元素」**的元素，也就是第一个>目标值的元素（当序列升序时）。

咱们结合你的两个查找需求具体分析：

需求1：找首个Bid≥Seek Bid的元素 #

如果你的谓词用<=，比如写成l.Bid <= target，那std::lower_bound会找第一个不满足这个条件的元素——也就是Bid>target的元素，这显然和你要的「首个≥target」不符。

比如测试数据中，当Seek Bid是80时，index8的Bid正好是80：

• 用l.Bid < 80作为谓词：index8的80不满足「<80」，所以lower_bound直接返回index8，符合预期。
• 用l.Bid <=80作为谓词：index8的80满足「<=80」，算法会继续往后找，直到找到index9的81（不满足<=80），返回的结果就错了。

需求2：找最后一个Ask≥Seek Ask的元素 #

因为Ask是降序排列的，你需要调整谓词适配降序逻辑。正确的做法是用std::upper_bound找第一个Ask<target的元素，再往前推一个就是最后一个≥target的元素。这里同样要用<而非<=：

• 用l.Ask < target作为谓词：upper_bound返回第一个Ask<target的元素，比如Seek Ask是70时，会找到index4的69，往前推一个就是index3的70（最后一个≥70的元素），符合预期。
• 如果用l.Ask <= target：upper_bound会返回第一个Ask<=target的元素（比如index2的70），往前推一个得到index1的71，这就不是你要的最后一个≥70的元素了。

本质上，STL的这两个查找算法是围绕「<」这个比较运算符设计的，它定义了序列的“顺序方向”。如果随意换成<=，就会打破算法原本的语义逻辑，导致结果偏离预期。

内容的提问来源于stack exchange，提问作者user1722025