Какова временная сложность для функции 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

Сложность

Количество выполненных сравнений - логарифмическое c на расстоянии между первым и последним (не более log2(last - first) + O(1) сравнений). Однако для не LegacyRandomAccessIterator s число приращений итератора является линейным.

^{(c) cppreference}

std::list итераторы не являются итераторами с произвольным доступом (они являются итераторами прямого доступа) ), поэтому сложность составляет O(n).