使用STL获得集合中最接近的元素

Question

我有一组（排序的）无符号整数，我需要找到最接近给定数字的元素。

我正在使用标准库寻找解决方案，我的第一个解决方案是使用二进制搜索，但是STL的实现仅在元素存在时返回。这篇文章Find Closest Element in a Set很有帮助，我基于std :: lower_bound方法实现了一个解决方案，

（*假设集合有2个以上的元素，则不进行空/边界检查）：

#include <iostream>
#include<set>
#include<algorithm>
#include<cmath>

int main()
{
    std::set<unsigned int> mySet = {34, 256, 268, 500, 502, 444};
    unsigned int searchedElement = 260;
    unsigned int closestElement;

    auto lower_bound = mySet.lower_bound(searchedElement);
    if (lower_bound == mySet.end()){
        closestElement = *(--lower_bound);
    }

    std::set<unsigned int>::iterator prevElement = --lower_bound;
    bool isPrevClosest = std::abs(*prevElement - searchedElement) > std::abs(*lower_bound - searchedElement);
    closestElement = isPrevClosest ? *prevElement : *lower_bound;

    std::cout << closestElement << std::endl;

    return 0;
}

是否有更简单，更标准的解决方案？

Answer 1

您可以使用std :: min_element（）：作为编译器，为其提供一个lambda值，例如，该值将返回绝对差异。

std::min_element(mySet.begin(), mySet.end(), [searchedElement](const unsigned int a, const unsigned int b) {
  return std::abs(searchedElement - a) < std::abs(searchedElement - b);
});

但是，我认为这将不再适用于二进制搜索...