我有一个向量，它包含了我的类X的许多元素。我需要找到一个元素在这个向量中的第一个出现，比如S，这样S.attrribute1>someVariable。someVariable不会被修复。如何对此进行二进制搜索？(不是c++11/c++14)。我可以用更大的搜索函数(理想情况下意味着检查相等性)编写std:：binary_search，但这是错误的吗？快速搜索的正确策略是什么？
根据二进制搜索的谓词，只有当向量按排序顺序时，才能执行二进制搜索。
因此，除非向量中">S.attribute1>someVariable"所在的所有元素都位于所有非元素之后，否则这将是一个不启动的过程。
如果向量中的所有元素都以其他方式排序，那么"其他方式"是唯一可以实现的二进制搜索。
假设它们是，你必须使用某种比较器，它在属性上指定严格的弱排序，以便首先得出你的排序向量：
class comparator {
public:
bool operator()(const your_class &a, const your_class &b) const
{
return a.attribute1 < b.attribute1;
}
};
诀窍是，如果你想单独使用属性值进行搜索，你需要使用一个可以与std::binary_search一起使用的比较器，其定义如下：
template< class ForwardIt, class T, class Compare > bool binary_search( ForwardIt first, ForwardIt last, const T& value, Compare comp );要使std:：binary_search成功，范围(first，last)必须为至少部分有序，即必须满足以下所有条件要求：
对于所有元素，如果元素<value或comp(元素，值)为true然后(value<element)或！comp(值，元素)也是真正的
因此，唯一的要求是comp(value, element)和comp(element, value)需要工作。您可以传递T的属性值，而不是要搜索的向量中的整个元素，只要您的比较器能够处理它：
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，并根据属性值进行二进制搜索。
而且，正如我所说，如果向量没有按给定的属性排序，那么所有的赌注都会落空。在这种情况下，您需要首先显式地使用std::sort，或者想出一些自定义容器，以正确的顺序，单独地跟踪矢量元素，并将其添加到容纳它们的主矢量中。也许使用指针，在这种情况下，您应该能够对指针本身执行二进制搜索，使用类似的搜索比较器来查看指针。
要使std::binary_search成功，需要对范围进行排序。CCD_ 9、CCD_。因此，每次在vector中添加新元素时，都需要对其进行排序。
为此，您可以在插入中使用std::lower_bound：
class X;
class XCompare
{
public:
bool operator()(const X& first, const X& second) const
{
// your sorting logic
}
};
X value(...);
auto where = std::lower_bound(std::begin(vector), std::end(vector), value, XCompare());
vector.insert(where, value);
同样，你可以使用std::lower_bound在你的矢量中搜索：
auto where = std::lower_bound(std::begin(vector), std::end(vector), searching_value, XCompare());
不要忘记检查std::lower_bound是否成功：
bool successed = where != std::end(vector) && !(XCompare()(value, *where));
或者，如果您只想知道元素在向量中，则直接使用std::binary_search。