在 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
https://stackoverflow.com/questions/68220759/
相关文章:
sql-server - 通过 docker 创建的默认 SQL Server 凭据是什么?
python - 如何将 {} 显示为 python f 字符串的一部分
php - 如何在 PHP 中验证 Google Cloud Services 中的服务帐户?
r - 您如何使用 Pearson 相关性来选择 `R` 中的特征?
bash - 动态提取 bash 中字符串列表中每个字符串唯一的模式
rust - 仅当处于 Release模式时,我如何在没有窗口的情况下运行 Rust 程序