列表类型的 binary_search 函数的时间复杂度是多少
What is the time complexity for binary_search function for a list type
是 O( n ) 还是 O( logn )？
list< int > myList = { 2, 6, 12, 13, 15, 18, 20};
cout << binary_search(myList.begin(), myList.end(), 20) ;
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).
是 O( n ) 还是 O( logn )？
list< int > myList = { 2, 6, 12, 13, 15, 18, 20};
cout << binary_search(myList.begin(), myList.end(), 20) ;
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).