如何使用二分查找法求 8 的平方根?保留 6 位小数。
假设只精确到整数部分
如果我们只需要计算整数部分的话,那很好实现,假设要开平方的数为 value
,依次二分,直到找到某一个整数的平方小于等于 value
,然后这个整数加1的平方大于 value
,那这个数就是开平方结果的整数部分了。
下面为 PHP 实现代码:
1 | function calcInteger($value, $low, $high) |
实现思路:
- 如果二分的中点的平方大于
value
,说明整数部分肯定位于中点之前。这个时候需要特别注意的是,不能直接calcInteger($value, 0, $mid - 1)
这样使用$mid - 1
作为下一次二分查找区间的上限,因为如果开平方结果带有小数的情况下,最终会陷入死循环(具体表现为,不断地在两个区间之间循环,比如[0, 3], [2, 3]
)。 - 如果位于中点之前,那么先判断 中点-1 的平方是否不大于
value
,那说明这个 中点-1 就是开平方结果的整数部分了 - 中点的平方小于
value
的情况也类似 - 如果中点的平方恰好等于
value
,那这个中点就是整数部分了。
再假设一下,精确到 1 位小数
这也好办,只要我们做平方操作的时候精确到 1 位小数就行了。如果中位数的平方大于 value
,这个时候就计算一下 $mid - 0.1
的平方,跟 value
做比较。我们在这种情况下,假设下一个比 $mid
小的数字为 $mid - 0.1
。
将一个整数之间的区间再细分成十份就很好理解了。
下面为 PHP 实现代码:
1 | function calcInteger($value, $low, $high) |
回到正题
按上一小节说的,我们如果要保留 6 位小数,则可以将原来一个整数的区间想象成有 1000000(10的6次方) 个小区间,比较的过程加减的粒度就是 10^-6 了。
下面为 PHP 实现代码:
1 | // 求 3 的平方根,保留 6 位小数 |
非递归实现
非递归实现的方式也挺简单的,只要在 $mid * $mid > $value
和 $mid * $mid < $value
两种情况下,分别修改一下区间的上限、下限即可。
1 | // 求 8 的平方根,保留 6 位小数 |
总结
本文求平方根的思想在于,将原来一个整数的区间拆分成多个小的区间,然后在所有的这些小区间里面依次二分找到最终合适的那个数。