为什么二分查找实际时间是阶跃函数，却被认定为O(log n)复杂度？

1. 先明确大O渐近记号的定义 #

大O记号从诞生起就不是用来描述精确运行时间的，它的核心作用是刻画「输入规模趋近于无穷大时，算法运行时间的增长上界」，计算过程会直接忽略所有常数项、低阶项，以及常数系数。
它的数学判定规则是：对于函数f(n)和g(n)，只要存在正的常数C和n₀，使得所有n ≥ n₀时都满足f(n) ≤ C * g(n)，就可以判定f(n) = O(g(n))。

2. 二分查找的精确运行次数完全符合O(log n)的判定 #

你观察到的二分查找最坏情况迭代次数是阶跃函数，本质是精确值为⌈log₂n⌉（对log₂n向上取整），这个值和log₂n的差值永远小于等于1，完全满足大O的判定条件：

• 当n ≥ 2时，1 ≤ log₂n，因此⌈log₂n⌉ ≤ log₂n + 1 ≤ log₂n + log₂n = 2 * log₂n
• 取常数C=2，n₀=2，完全符合大O的判定规则，因此⌈log₂n⌉ = O(log n)

3. 阶跃特征不影响复杂度分类 #

你观察到的阶跃是实际运行时必须取整数次迭代带来的常数级误差，当输入规模n足够大时，这个最多为1的误差和log n的增长幅度相比可以完全忽略，两者的增长速率完全一致，没有出现更快的增长趋势，因此不会改变复杂度的分类。
另外对数的底数在大O记号中可以直接省略，因为不同底数的对数之间仅相差常数系数，会被大O规则直接忽略。

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