c++ - 在 log(n) 时间内获取对已排序向量中元素的迭代器。

Question

我有一个排序的向量，想在其中找到一个特定的元素。我可以使用binary_search它，但它只告诉它是否存在。我还需要一个迭代器来访问该元素。有没有一种简单的方法，或者我必须按顺序搜索它。

任何帮助表示赞赏。

Answer 1

Look into lower_bound and upper_bound. lower_bound gives the iterator to the first matching element while upper_bound gives the iterator one past the last matching element.

If either algorithm fails to find a match, it returns an iterator to the place where the item could be inserted to maintain a sorted container.

I've always felt binary_search was misleadingly named.

Answer 2

std::lower_bound将返回不小于您的值的第一个元素。意思是如果返回的元素等于你的值，你的好，如果它不相等或结束迭代器比正确的元素还没有找到。

这是来自骗子的代码

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}

请记住，如果您使用std::upper_boundthan 它会返回第一个更大的元素，因此不太容易适应您的目的，因为如果确实找到了您的元素，您必须减少迭代器，即使那样您仍然可能找不到它