二分查找在1000元素与100万元素数组上的耗时计算问题

预计耗时计算 #

二分查找的时间复杂度为O(log₂n)，每次比较会把待搜索的区间缩小一半，运行耗时仅和比较次数正相关：

• 1000个元素时，log₂(1000)≈10，最多需要10次比较就能完成查找，对应你机器上的耗时是1秒
• 100万个元素时，log₂(1000000)≈20，最多需要20次比较就能完成查找

按比例换算下来，同机器上100万元素的二分查找预计耗时为2秒左右。

相关疑问解答 #

百万级数组的二分查找耗时一定比千级数组更长吗？ #

理论上是的，但实际差异可能非常小，甚至会出现偶发的持平/更短情况：

• 二分查找的比较次数增长极慢，哪怕元素规模从1000涨到10亿，也仅需要多做10次比较
• 实际运行中的缓存命中、CPU调度优先级、后台进程占用等偶然因素，可能会抹平这几次比较的耗时差异，属于正常的运行波动，不违反算法的时间复杂度规律。

耗时结果会受计算机本身性能影响吗？ #

一定会。你测得的1秒本身就是慢机器的结果，同样的代码放到性能更高的设备上，1000元素的二分查找耗时可能只有几微秒，100万元素的耗时也不会超过几十微秒。但只要是在同一台设备的稳定运行环境下，100万元素的查找耗时大概是1000元素场景的2倍这个比例是固定的，不受设备性能影响。

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