列表类型的Lower_bound函数的时间复杂度是多少

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

复杂度

执行的比较次数是第一个和最后一个之间的距离的对数（最多log2(last - first) + O(1)个比较）。但是，对于非LegacyRandomAccessIterator，迭代器增量的数量是线性的。

^{（c）cppreference}

[std::list迭代器不是随机访问迭代器（它们是转发迭代器），所以复杂度为O(n)。