为何1-100随机数猜数游戏的二分查找模拟平均步数趋近于5.8左右？

嗨，这个问题问得特别好！你看到的5.8可不是什么随机出现的数字，它就是这个猜数游戏用二分法的理论平均步数，当你模拟的次数越多，样本的平均值自然就会无限接近这个准确值。

我给你拆解一下这个数字怎么来的：

• 二分法的核心是每次把搜索区间砍半，每猜一次要么直接命中，要么把剩余范围缩小一半。但100不是2的整数次幂（2^6=64，27=128），所以不同数字需要的步数不一样：
  • 只有数字50能1次就猜中（第一次就猜区间中间值）
  • 数字25、75需要2次（第一次猜50错了，第二次猜新区间的中间值就中了）
  • 更多数字需要3、4、5、6次，甚至像100这种极端值需要7次才能猜中
• 要算出理论平均值，我们把1到100每个数字的猜中步数全部加起来，再除以100。用递推的方法算下来，所有数字的步数总和刚好是580，580除以100就是刚好5.8。
• 简单说就是，大部分数字需要5-6步，少数极端值需要7步，平均下来就落到了5.8这个点上。

另外你观察到的“模拟次数越多越接近5.8”，其实就是大数定律的体现——样本量越大，样本平均值就越贴近真实的理论平均值，就像你抛硬币抛得越多，正面朝上的比例越接近0.5是一个道理。

备注：内容来源于stack exchange，提问作者Muhammad Umer