c++ - STL 中的 find() 与 binary_search()

Question

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

Answer 1

简单的答案是: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