降序排列数组中二分查找失败时的平均时间复杂度是多少

题目 #

当数组内的数字按降序排列、且查找操作未命中时，二分查找的平均时间复杂度为多少？请选出以下正确答案：
(a) log₂(n+1)
(b) log₂(n)
(c) log₂(n²)
(d) 以上都不对

正确答案 #

选 （b）log₂(n)

解析 #

• 二分查找的效率只和数组的有序性有关，和数组是升序还是降序排列没有关系，降序场景下只需要把比较判断的逻辑反转，不会改变每轮缩小一半查找区间的逻辑，也不会改变查找次数。
• 不管是命中还是未命中场景，二分查找每轮都会把待查找区间砍掉一半，平均情况下只需要*log₂(n)*量级的比较就能得出结果。
• 其他选项错误原因：
  • 选项a是二分查找最坏情况的查找次数近似值，不是平均时间复杂度
  • 选项c的量级为O(n)，完全不符合二分查找的效率特征

内容的提问来源于stack exchange，提问作者Amazon King