Skip to content

Latest commit

 

History

History
9 lines (9 loc) · 1.29 KB

在C++的算法库中,find()和binary_search()有什么区别?.md

File metadata and controls

9 lines (9 loc) · 1.29 KB
  1. 算法复杂度和预期使用场景:
    • find() 函数执行线性查找。它逐个检查容器中的元素,直到找到等于指定值的元素或结束。因为它是通过遍历实现的,所以其时间复杂度为 O(n),其中 n 是容器中元素的数量。find() 不要求容器中的元素是事先排序的。
    • binary_search() 函数执行二分查找。它要求容器中的元素已经按非降序排序,并且通过不断将搜索范围缩小一半来查找特定值。因此,其时间复杂度为 O(log n) 。由于这种查找方式依赖于容器的元素顺序,所以在未排序的容器上使用 binary_search() 会得到未定义的行为。
  2. 返回值:
    • find() 返回一个迭代器,指向在容器中找到的第一个等于指定值的元素。如果没有找到,它返回一个等于 end() 迭代器的值。
    • binary_search() 返回一个布尔值,如果找到指定值则返回 true,否则返回 false。注意,它并不返回目标元素的位置或迭代器。
  3. 通用性:
    • find() 可以用于任何类型的容器,包括列表、向量、集合等,而且不需要元素是排序的。
    • binary_search() 通常用于数组或向量等随机访问容器,并且前提是这些容器中的元素已经被排序。