O(N) 查找，但在排序列表上使用 upper_bound 时进行 O(log(N)) 比较

Question

list<Person> lp;
...
lp.sort(PersonNameLess());
Person newPerson;
...
lp.insert(upper_bound(lp.begin(), lp.end(), 
          newPerson, PersonNameLess()), newPerson);

在有效的 c++ 第 3 版第 198 页第 45 项中，它说：

查找需要线性时间，但它只执行对数 比较次数

问题：为什么它只执行对数比较？

Answer 1

为什么它只执行

对数比较？

因为列表已排序，upper_bound执行二叉搜索。