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

Question

我需要一个二进制搜索功能。

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

我要寻找的功能是什么？

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

Answer 1

我敢肯定，标准库不包含任何可以完全满足您要求的内容。

要获得所需的内容，您可能要从std::lower_bound或开始std::upper_bound，并将其返回的迭代器转换为索引，然后对找不到值的索引进行补充。

Answer 2

据我所知，没有简单的 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 3

这段代码应该可以正常工作

auto itr = lower_bound(v.begin(), v.end(), key) ;
index = distance(v.begin(), itr);

有关 std::lower_bound() 的更多信息 - https://www.geeksforgeeks.org/stdlower_bound-in-c/