STL＆QUOT;最接近＆QUOT;方法？ [英] STL "closest" method?

问题描述

我在找一个STL的排序，如果准确值是不是在容器present返回元素最接近的目标值。它需要要快，所以基本上我正在寻找一个稍微修改的二进制搜索...我可以写，但似乎喜欢的事，应该已经存在...

I'm looking for an STL sort that returns the element "closest" to the target value if the exact value is not present in the container. It needs to be fast, so essentially I'm looking for a slightly modified binary search... I could write it, but it seems like something that should already exist...

推荐答案

你的意思是 LOWER_BOUND / UPPER_BOUND 功能？这些执行二进制搜索，返回你正在寻找的价值高于最接近的元素。

Do you mean the lower_bound/upper_bound functions? These perform a binary search and return the closest element above the value you're looking for.

澄清：较低的全球版本/ UPPER_BOUND只有在范围进行排序，工作，因为他们使用某种二进制搜索的内部。 （显然，性病::地图的下限/ UPPER_BOUND方法总是工作）。你在你的问题，你在寻找某种二进制搜索的说，所以我会承担的范围内进行排序。

Clarification: The global versions of lower/upper_bound only work if the range is sorted, as they use some kind of binary search internally. (Obviously, the lower/upper_bound methods in std::map always work). You said in your question that you were looking for some kind of binary search, so I'll assume the range is sorted.

此外，无论是 LOWER_BOUND 也不 UPPER_BOUND 返回最接近的成员。如果该值 X 你要找的是不是范围中的一员，他们都将返回的第一个元素大于 X 。否则， LOWER_BOUND 将返回等于 X中的第一个值， UPPER_BOUND 将返回最后值等于 X 。

Also, Neither lower_bound nor upper_bound returns the closest member. If the value X you're looking for isn't a member of the range, they will both return the first element greater then X. Otherwise, lower_bound will return the first value equal to X, upper_boundwill return the last value equals X.

因此​​，要找到最接近的值，你就必须

So to find the closest value, you'd have to

• 通话 LOWER_BOUND


• 如果它返回的范围的结束，所有值都小于 X 。最后（即最高）元素是最接近的一个


• ，如果返回范围的开始，所有的值都大于 X 。第一个（即最低）元素是最接近的一个


• 如果它返回的范围中间的元素，检查元素与之前的元素 - 一个最贴近 X 就是你要找的人

• call lower_bound
• if it returns the end of the range, all values are less then X. The last (i.e. the highest) element is the closest one
• it if returns the beginning of the range, all values are greater then X. The first (i.e. the lowest) element is the closest one
• if it returns an element in the middle of the range, check that element and the element before - the one that's closer to X is the one you're looking for

这篇关于STL＆QUOT;最接近＆QUOT;方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！