在向量中找到最近的点

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

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

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

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

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

感谢大家,

戴夫

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

double val = 45;
double lower, upper;
std::vector::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;
}

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

您可以简单地使用二进制搜索,它将在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