STL 中的 find() 与 binary_search()

Question

哪个函数在向量find()或binary_search()中搜索元素时更有效？

Answer 1

简单的答案是：std::find对于未排序的数据和std::binary_search排序的数据。但我认为这还有更多内容：

[start, end)两种方法都采用包含n元素和值的范围x作为输入。但请注意一个重要的区别，即std::binary_search 仅返回 abool来告诉您范围是否包含该元素。std::find()返回一个迭代器。因此两者都有不同但重叠的用例。

std::find()非常简单。O(n)迭代器增量和O(n)比较。输入数据是否排序并不重要。

因为std::binary_search()你需要考虑多个因素：

• 它仅适用于排序数据。您需要考虑分类成本。

• 比较次数始终为O(log n)。

• 如果迭代器不满足LegacyRandomAccessIterator迭代器增量的数量为O(n)，则当满足此要求时，它将是对数的。

结论（有点固执己见）：

• 当您操作未排序的数据或需要您搜索的项目的位置时，您必须使用std::find()
• 当您的数据已经排序或需要排序并且您只想检查元素是否存在时，请使用std::binary_search()
• 如果您想搜索像 这样的容器std::set，std::map或者它们的无序对应容器，也可以考虑它们的内置方法，比如std::set::find