在 vector find() 或 binary_search() 中搜索元素时，哪个函数更有效？
最佳答案
简单的答案是:std::find 用于未排序的数据，std::binary_search 用于排序的数据。但我认为这还不止于此:
这两种方法都采用包含 n 元素的范围 [start, end) 和将作为输入找到的值 x。但请注意 std::binary_search 仅返回一个 bool 的重要区别，它告诉您该范围是否包含该元素。 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
关于c++ - STL 中的 find() 与 binary_search()，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/68220759/