为何二分查找的时间复杂度被认定为Θ(logn)？

首先纠正一个关键误区：Θ符号的紧界判定是针对同一个分析场景的，不是把最好和最坏情况混在一起谈。你提到的“最坏O(logn)+最好Ω(logn)”是错误的逻辑，正确的逻辑是：针对某一种场景（比如最坏情况、平均情况），该场景下的时间复杂度T(n)同时满足O(logn)和Ω(logn)，才能说这个场景的复杂度是Θ(logn)。

以下分点拆解你的疑问：

• Θ符号的核心定义：如果存在正常数c1、c2和n0，使得对于所有n≥n0，都有c1*logn ≤ T(n) ≤ c2*logn，那么T(n)就是Θ(logn)。这个定义是针对同一个场景下的T(n)，而非跨场景混合。
• 二分查找的不同场景复杂度：
  • 最好情况：目标元素正好在数组中间，一次比较就找到，此时T(n)=1，显然满足Θ(1)（既O(1)又Ω(1)）。
  • 最坏情况：目标元素不在数组中，或者在数组的最边缘，每次都要把数组分成两半直到只剩一个元素，递推式为T(n) = T(n/2) + 1，解为T(n) = log₂n + 1。这个结果完全符合Θ(logn)的定义——当n≥2时，log₂n ≤ log₂n+1 ≤ 2log₂n，上下都有紧界。
  • 平均情况：假设目标元素在数组中的每个位置概率相等，计算平均比较次数后会发现，结果也是Θ(logn)。
• 为什么大家说二分查找是Θ(logn)：算法复杂度的讨论如果没有特别说明，默认指最坏情况复杂度——因为我们需要保证算法在最极端场景下的性能下限和上限，这是工程实践中最有参考价值的指标。所以当提到二分查找是Θ(logn)时，默认指的是最坏（或平均）情况的紧界，和最好情况的Θ(1)并不冲突。

你并没有搞错Θ符号的定义，只是混淆了“不同场景的复杂度”和“行业默认的复杂度表述惯例”。二分查找在不同场景下有不同的紧界，而我们常说的Θ(logn)是针对最坏/平均情况的结论。

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