在STL中使用返回的索引进行二进制搜索？

Question

我需要二进制搜索功能。

我在标准库中找不到任何将返回找到的项的索引的函数，如果找不到，将返回下一个元素的索引的按位补码，该元素大于我查找的项目。

我在寻找什么功能？

编辑：我需要将一个项目插入到已排序的向量中并保持其排序。这就是为什么我需要按位补充索引。

Answer 1

我非常肯定标准库不包含任何你正在要求的东西。

为了获得你想要的东西，你可能想要从std::lower_bound或std::upper_bound开始，并将它返回的迭代器转换为索引，然后补充未找到的值的索引。

Answer 2

很明显，这个“将返回按位补码”对你来说是一个大问题，我不明白你的意思。也就是说，查找std::upper_bound并查看它是否符合您的要求。

Answer 3

据我所知，没有简单的STL方法可以对已排序的向量返回索引，但是您可以使用下面的示例函数：

/**
 * @param v - sorted vector instance
 * @param data - value to search
 * @return 0-based index if data found, -1 otherwise
*/
int binary_search_find_index(std::vector<int> v, int data) {
    auto it = std::lower_bound(v.begin(), v.end(), data);
    if (it == v.end() || *it != data) {
        return -1;
    } else {
        std::size_t index = std::distance(v.begin(), it);
        return index;
    }   
}

Answer 4

使用STL我们可以找到索引

vector<int> vec{1,2,3,4,5,6,7,8,9} ;
vector<int> :: iterator index;
index=lower_bound(vec.begin(),vec.end(),search_data);
return (index-vec.begin());

Answer 5

int bin_search (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator low;
  low = std::lower_bound(first,last,val);
  if(low!=last && !(val<*low)){
    return (low - first + 1);
  }else{
    return 0;
  }
}