百万有序无重复数组中，二分查找随机存在值的平均中点检查次数

问题描述 #

假设目标值存在且随机，在包含100万个有序无重复int的数组中，使用以下二分查找代码查找时，平均会检查多少次中点？已知当目标值不存在时，每次都会检查约20次（log₂(1,000,000)≈20），因为永远找不到目标值。那么当目标值存在时，平均检查次数是否仍接近20次？原因是什么？

二分查找代码 #

int binarySearch(int array[], int find, int low, int high) {
  while(low <= high) {
    int mid = low + (high - low) / 2;
    if(array[mid] == find) {
      return mid;
    } else if(array[mid] < find) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

分析与结论 #

平均检查次数计算 #

对于有序无重复数组，二分查找的过程可以对应一棵二叉搜索树：每个数组元素对应树中的一个节点，节点的深度就是找到该元素需要检查的中点次数（根节点深度为1，对应第一次检查中点）。

100万近似等于2^20（实际2^20=1048576），我们可以近似计算：

• 前19层是满二叉树，总节点数为2^19 - 1 = 524287，这些节点的总检查次数为：1*1 + 2*2 + 3*4 + ... + 19*2^18 = (19-1)*2^19 + 1 = 9437185
• 剩余的1000000 - 524287 = 475713个元素位于第20层，每个需要检查20次，总检查次数为475713*20 = 9514260

总检查次数为9437185 + 9514260 = 18951445，平均检查次数为18951445 / 1000000 ≈ 18.95次。

是否接近20次？原因是什么？ #

平均次数接近20次但略小，原因如下：

• 当目标存在时，只要找到匹配的中点就会立即返回，不需要完成所有log₂(n)次检查。而目标不存在时，必须循环到low > high才会终止，一定会执行约20次检查。
• 由于100万非常接近2^20，大部分元素（约52%）需要19次以内的检查，剩下的48%需要20次检查，整体平均值会略低于20，但差距很小，所以仍然接近20次。

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