在向量中找到最近的点

Question

给定具有多个值的排序向量,如以下示例所示:

std::vector<double> f;
f.pushback(10);
f.pushback(100);
f.pushback(1000);
f.pushback(10000);

我正在寻找最优雅的方法来检索任何双d紧邻它的两个值.例如,给定值"45",我希望返回"10"和"100".

我看着lower_bound和upper_bound,但他们没有做我想要的.你能帮我吗？

编辑:我已经决定发布我自己的anser,因为它有点是我在这个帖子中得到的所有有用答案的组合.我已经投了那些我认为最有帮助的答案.

感谢大家,

戴夫

Answer 1

您可以使用STL的lower_bound来获得您想要的几行代码.lower_bound在底层使用二进制搜索,因此您的运行时为O(log n).

double val = 45;
double lower, upper;
std::vector<double>::iterator it;
it = lower_bound(f.begin(), f.end(), val);
if (it == f.begin()) upper = *it; // no smaller value  than val in vector
else if (it == f.end()) lower = *(it-1); // no bigger value than val in vector
else {
    lower = *(it-1);
    upper = *it;
}

Answer 2

您可以使用equal_range()在一次调用中获取这两个值(如果存在).它返回一个std ::对迭代器,第一个是第一个位置,第二个是你可以在不违反排序的情况下插入传递值的最后一个位置.要严格满足您的标准,在验证它不等于向量的begin()之后,您必须首先递减迭代器.

Answer 3

您可以简单地使用二进制搜索,它将在O(log(n))中运行.

这是一个Lua片段(我没有时间在C++中做,对不起),它可以做你想要的,除了限制条件(你还没有定义):

function search(value, list, first, last)
    if not first then first = 1; last = #list end

    if last - first < 2 then
        return list[first], list[last]
    end

    local median = math.ceil(first + (last - first)/2)

    if list[median] > value then
        return search(value, list, first, median)
    else
        return search(value, list, median, last)
    end
end

local list = {1,10,100,1000}

print(search(arg[1] + 0, list))

它从命令行搜索值:

$ lua search.lua 10 # didn't know what to do in this case
10  100
$ lua search.lua 101
100 1000
$ lua search.lua 99
10  100

Answer 4

我将发布我自己的答案，并对任何帮助我实现这一目标的人进行投票，因为这是我最终将使用的，并且你们都帮助我得出了这个结论。欢迎评论。

std::pair<value_type, value_type> GetDivisions(const value_type& from) const
{
    if (m_divisions.empty())
        throw 0; // Can't help you if we're empty.

    std::vector<value_type>::const_iterator it = 
        std::lower_bound(m_divisions.begin(), m_divisions.end(), from);

    if (it == m_divisions.end())
        return std::make_pair(m_divisions.back(), m_divisions.back());
    else if (it == m_divisions.begin())
        return std::make_pair(m_divisions.front(), m_divisions.front());
    else
        return std::make_pair(*(it - 1), *(it));
}