如何理解二分查找最坏情况时间复杂度O(log₂n)的逻辑

前置前提 #

二分查找仅适用于有序数组，核心逻辑是每次取当前区间的中间元素和目标值比较，直接排除掉一半不相关的元素，将待查找区间缩小为原来的1/2。

最坏情况定义 #

最坏情况指的是目标元素不在数组中，或者刚好位于待查找区间的端点位置，需要完成所有拆分比较操作才能得到结果。

逐步推导过程 #

• 设初始待查找区间的元素总数为n，最坏情况下一共需要执行k次比较操作才能得到结果
• 每完成1次比较，待查找区间的长度就会缩小为原来的1/2，执行k次后，剩余的待查找区间长度最多为1（再执行1次比较就能确定是否匹配，或者区间失效返回结果）

因此可以得到不等式：

n / 2^k ≤ 1

对不等式做变形：

1. 两边同时乘以2^k，得到 n ≤ 2^k
2. 两边同时取以2为底的对数，得到 log₂n ≤ k

也就是说最坏情况下的比较次数k至少为log₂n（非整数的情况下向上取整）。

复杂度结论 #

大O表示法会忽略常数系数和低阶项，因此二分查找最坏情况下的时间复杂度为O(log₂n)，日常表述中也经常简写为O(log n)（不同底数的对数之间仅相差常数系数，不会影响复杂度的量级判断）。

和伪代码的对应说明 #

你给出的递归版二分查找伪代码如下：

binarySearch( list, value, low, high ){ 

  if low <= high { 
     mid = (low + high)/ 2

     if value == list[mid]
         return mid

      else if value < list[mid]
         return binarySearch( list, value, low, mid - 1 )

      else
          return binarySearch( list, value, mid+1, high)
      } 

  else
  return -1 
}

每一次递归调用时，待查找区间都会被替换为左半区间或者右半区间，区间长度直接减半，递归的深度就是我们上面推导的比较次数k，量级为log₂n，和推导结论完全匹配。

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