二分法查找——对数_二分法查找log2

作者：笔触狂放9 | 2024-05-26 01:09:25

踩

二分法查找log2

对于有序数组,使用二分法查找数据比较的次数

范围需要次数

10 4

100 7

1000 10

10000 14

100000 17

1000000 20

除了对特别小的数组外,二分法查找表现是非常优秀的.

每次对范围加倍可以创建出一个数列,它是2的幂,假设s表示步数,r表示范围,则有

r=2s

当我们知道查找的范围r,求步数s时.就是相当于求某数指数函数的反函数即对数.则公式表示为:

s=log2(r)

如何计算呢,大多数计算器都有log功能,通常是以10为底来求对数,但是通过结果乘以3.322可以转换成以2为底的对数

log10(100)=2;log2(100)=2乘以3.322 = 6.644 四舍五入为7正好是上面数据对照表100对应的7次

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/624487