std::lower_bound调用异常排查：高斯型数据找最近值失败问题

问题背景 #

正在处理包含频率和电压两列的数据，需要查找与给定值val最接近的数值。由于数据呈高斯分布，最大值上下各有一个符合条件的数值。将电压列存入vector并编写查找函数后，结果不符合预期，尤其是最大值下方区域的结果错误。

现有代码 #

#include<iostream>
#include<vector>
#include<cmath>

typedef std::vector <double> vector;

vector posi(vector vec, int ref, double val);

int main(void){

  //define a custom volt vector here e.g vector volt{...};
  auto auxvmax = std::max_element(volt.begin(), volt.end());
  int posvmax = auxvmax - volt.begin();//this is what I take as ref value
  
  double val = 0.7;
  vector fpos(2, 0.0);
  fpos = posi(volt, posvmax, val);
  double auxf_1 = fpos[0];
  double auxf_2 = fpos[1];
  std::cout << "closest value to " << val << " are " << volt[auxf_1] << " below and " << volt[auxf_2] << " above\n";
return 0;
}

vector posi(vector vec, int ref, double val){

  vector posvec(2, 0.0);
  auto pos1 = std::lower_bound(vec.begin(), vec.begin() + ref, val);
  auto pos2 = std::lower_bound(vec.begin() + ref, vec.end(), val);

  double val1a = *(pos1 - 1.0);
  double val1b = *pos1;
  double val2a = *(pos2 - 1.0);
  double val2b = *pos2;

  if(fabs(val - val1a) < fabs(val - val1b)){
    posvec[0] = pos1 - vec.begin() - 1;
  }
  if(fabs(val - val1a) > fabs(val1b)){
    posvec[0] = pos1 - vec.begin();
  }
  if(fabs(val - val2a) < fabs(val - val2b)){
    posvec[1] = pos2 - vec.begin() - 1;
  }
  if(fabs(val - val2a) > fabs(val - val2b)){
    posvec[1] = pos2 - vec.begin();
  }

  return posvec;
}

输出结果 #

closest values to 0.7 are 0.485437 below, and 0.320388 above
0.485437
0.500971
0.524272
0.543689
0.563107
0.594175
0.617476
0.648544
0.679612
0.71068
0.741748
0.786408
0.825243
0.864078
0.893204
0.932039
0.961165
0.980583
0.990291
1
0.990291
0.961165
0.941748
0.893204
0.854369
0.805825
0.757282
0.708738
0.669903
0.621359
0.582524
0.547573
0.512621
0.481553
0.454369
0.427184
0.403883
0.384466
0.361165
0.341748
0.320388

核心错误分析 #

1. std::lower_bound适用条件违规：最大值上方的区域（vec.begin()+ref到vec.end()）是降序排列，但std::lower_bound默认仅支持升序序列，直接调用会导致查找结果完全错误。
2. 比较逻辑笔误：判断左半区第二个条件时，写成了fabs(val - val1a) > fabs(val1b)，正确应为fabs(val - val1a) > fabs(val - val1b)，少了val -导致比较逻辑失效。
3. 未处理边界越界：当pos1指向vec.begin()或pos2指向vec.end()时，pos1-1、pos2-1会导致数组越界访问。
4. 索引类型错误：用vector<double>存储整数索引，后续访问volt[auxf_1]会触发隐式转换，存在潜在风险。

修复后的代码 #

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

typedef std::vector<double> vector;

std::vector<int> posi(const vector& vec, int ref, double val);

int main(void){
  // 示例数据
  vector volt = {
    0.485437,0.500971,0.524272,0.543689,0.563107,0.594175,0.617476,0.648544,0.679612,0.71068,
    0.741748,0.786408,0.825243,0.864078,0.893204,0.932039,0.961165,0.980583,0.990291,1,
    0.990291,0.961165,0.941748,0.893204,0.854369,0.805825,0.757282,0.708738,0.669903,0.621359,
    0.582524,0.547573,0.512621,0.481553,0.454369,0.427184,0.403883,0.384466,0.361165,0.341748,0.320388
  };

  auto auxvmax = std::max_element(volt.begin(), volt.end());
  int posvmax = auxvmax - volt.begin();
  
  double val = 0.7;
  auto fpos = posi(volt, posvmax, val);
  int auxf_1 = fpos[0];
  int auxf_2 = fpos[1];
  std::cout << "closest value to " << val << " are " << volt[auxf_1] << " below and " << volt[auxf_2] << " above\n";
  return 0;
}

std::vector<int> posi(const vector& vec, int ref, double val){
  std::vector<int> posvec(2, -1);

  // 处理左半区（升序）
  if(ref > 0){
    auto pos1 = std::lower_bound(vec.begin(), vec.begin() + ref, val);
    int candidate1 = -1;
    int candidate2 = -1;

    if(pos1 == vec.begin()){
      candidate1 = pos1 - vec.begin();
    } else if(pos1 == vec.begin() + ref){
      candidate1 = ref - 1;
    } else {
      candidate1 = pos1 - vec.begin() - 1;
      candidate2 = pos1 - vec.begin();
    }

    if(candidate2 != -1){
      posvec[0] = fabs(val - vec[candidate1]) < fabs(val - vec[candidate2]) ? candidate1 : candidate2;
    } else {
      posvec[0] = candidate1;
    }
  }

  // 处理右半区（降序），使用自定义比较器
  if(ref < vec.size()){
    auto pos2 = std::lower_bound(vec.begin() + ref, vec.end(), val, 
                                [](double a, double b){ return a > b; });
    int candidate1 = -1;
    int candidate2 = -1;

    if(pos2 == vec.begin() + ref){
      candidate1 = pos2 - vec.begin();
    } else if(pos2 == vec.end()){
      candidate1 = vec.size() - 1;
    } else {
      candidate1 = pos2 - vec.begin() - 1;
      candidate2 = pos2 - vec.begin();
    }

    if(candidate2 != -1){
      posvec[1] = fabs(val - vec[candidate1]) < fabs(val - vec[candidate2]) ? candidate1 : candidate2;
    } else {
      posvec[1] = candidate1;
    }
  }

  return posvec;
}

修复说明 #

1. 适配降序序列：右半区使用带自定义比较器的std::lower_bound，比较逻辑为a > b，匹配降序数据的查找需求。
2. 修正比较逻辑：修复笔误，确保比较的是目标值与候选值的差值绝对值。
3. 边界情况处理：判断查找迭代器是否指向序列首尾，避免越界访问。
4. 索引类型修正：改用std::vector<int>存储索引，消除浮点类型转换风险。
5. 性能优化：函数参数传递const vector& vec，避免不必要的容器拷贝。

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