c++ - 对大于属性的元素的 vector 对象进行二进制搜索

Question

我有一个 vector ，其中包含我的 X 类的很多元素。我需要找到该 vector 中第一次出现的元素，例如 S，使得 S.attrribute1 > someVariable。 someVariable 不会固定。我该怎么做 binary_search？ (不是 c++11/c++14)。我可以编写带有更大搜索功能的 std::binary_search(理想情况下意味着检查相等性)，但那是错误的吗？快速搜索的正确策略是什么？

Answer 1

根据定义，只有当 vector 按根据二分搜索谓词排序的顺序时才能进行二分搜索。

所以，除非你的 vector 中的所有元素“S.attribute1 > someVariable”都位于所有不是的元素之后，否则这将是一个非启动器，就在门。

如果 vector 中的所有元素都以其他方式排序，则“其他方式”是唯一可以实现的二进制搜索。

假设它们是，您必须使用某种比较器，它在属性上指定严格的弱排序，以便首先得出您的排序 vector :

class comparator {

public:
    bool operator()(const your_class &a, const your_class &b) const
    {
          return a.attribute1 < b.attribute1;
    }
};

诀窍在于，如果您想单独使用属性值进行搜索，则需要使用可与 std::binary_search 一起使用的比较器，即 defined as follows :

template< class ForwardIt, class T, class Compare >
bool binary_search( ForwardIt first, ForwardIt last,
                    const T& value, Compare comp );

For std::binary_search to succeed, the range [first, last) must be at least partially ordered, i.e. it must satisfy all of the following requirements:

for all elements, if element < value or comp(element, value) is true then !(value < element) or !comp(value, element) is also true

因此，唯一的要求是 comp(value, element) 和 comp(element, value) 需要工作。您可以传递 T 的属性值，而不是要搜索的 vector 中的整个元素，只要您的比较器可以处理它:

class search_comparator {

public:
    bool operator()(const your_class &a, const attribute_type &b) const
    {
          return a.attribute1 < b;
    }

    bool operator()(const attribute_type &a, const your_class &b) const
    {
          return a < b.attribute1;
    }
};

现在，您应该能够使用 search_comparator 而不是 comparator，并通过属性值进行二分查找。

而且，正如我所说，如果 vector 未按给定属性排序，则所有赌注都将取消。在这种情况下，您需要先明确地使用 std::sort ，或者想出一些自定义容器来跟踪 vector 元素，以正确的顺序，单独和另外到持有它们的主要 vector 。也许使用指针，在这种情况下，您应该能够对指针本身执行二进制搜索，使用类似的搜索比较器来查看指针。