c++ - 对排序 vector 进行二分查找

Question

template <class T, class C>
size_t idx(const std::vector< T >& elements, const C& val)
{
  if (val<elements[0]||val==elements[0])
    return 0;
  int s=elements.size();
  if (val>elements[s-1])
    return s;
  int min=0;
  int max=s-1;
  int mid;
  while (max >= min){
      mid=(max+min)/2;
      if (val<elements[min])
          return min;
      else if (val>elements[max])
          return max+1;
      else if((val==elements[mid])||((val>elements[mid-1])&&(val<elements[mid])))
          return mid;
      else if((val>elements[mid])&&(val<elements[mid+1]))
          return mid+1;
      else if (val>elements[mid+1])
          min=mid+1;
      else 
            max=mid-1;
    }
    return max;
}

这与btree有关。元素 vector 被排序。我想在这个 vector 上找到插入点，如果值恰好在 vector 中，则返回它的索引。此外，例如，大小为 7 的 vector 上有 8 个插入点。我一直遇到段错误，我认为这可能是一个:因一个错误或类似错误而关闭，有人可以帮忙吗？谢谢。

Answer 1

如果 vector 大小为 2，则 min == mid == 0 和 max == 1。在代码中，您检查 mid - 1 处的元素，即 -1，因此您的程序表现出未定义的行为。