std:find() 用于排序与未排序

Question

考虑两个整数向量v1和v2，其中v1已排序和v2未排序。使用 搜索这两个向量中的元素的时间复杂度是find()多少？

Answer 1

std::find()执行线性搜索，即它逐个元素地查找，直到找到它要查找的值。无论集合是否排序，它都是线性的。

如果您有一个已排序的向量，您可能需要考虑使用二分搜索来std::lower_bound()代替。这将是向量大小的对数。