c++ - 列表类型的binary_search函数的时间复杂度是多少

Question

是 O( n ) 还是 O( logn ) ？

  list< int > myList = { 2, 6, 12, 13, 15, 18, 20};    
    cout << binary_search(myList.begin(), myList.end(), 20) ;

Answer 1

Complexity

The number of comparisons performed is logarithmic in the distance between first and last (At most log2(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, number of iterator increments is linear.

^{(c) cppreference}

std::list 迭代器不是随机访问迭代器(它们是前向迭代器)，因此复杂度为 O(n)。