二分查找的平均时间复杂度是否可表示为Ω(log n)？

结论：二分查找的平均时间复杂度确实是Ω(log n)，原因如下：

• 先明确Ω符号的定义：它代表算法运行时间的渐近下界，即存在常数c>0和足够大的n₀，当n≥n₀时，算法的平均运行时间T(n) ≥ c·log n。

• 从算法逻辑看，二分查找每次通过比较将搜索空间缩小一半。无论目标元素存在与否，要从n个元素中定位目标（或确定不存在），信息论层面至少需要log₂n次二元判断（每次比较就是一次二元选择：目标在左半区间还是右半区间）。这种底层的判断次数下限，直接决定了平均情况下不可能用远少于log n的步骤完成查找。

• 结合平均情况的计算：假设数组元素均匀分布，统计所有可能查找场景的平均比较次数，结果会是与log n成正比的数值（比如约为log₂n - 1），完全满足Ω(log n)的定义——存在固定常数c（比如取c=0.5），当n足够大时，平均运行时间始终不低于c·log n。

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