你好，我是zhenguo
这是我的第507篇原创
前几天有朋友问我，面试遇到一道题目，看似简单，但是最后没有写好。
这道题目描述简单，就是使用二分法对非负数开根号，并返回。
中午我实现了一版，截止目前测试没有发现问题。
基本实现思路是这样：
  • 先初步确定开根号所在的一个大概区间[a,b]
  • 然后使用二分法，逐次迭代

详细实现

下面我详细介绍下上面两个步骤。
第一步，初步确定开根号所在的一个大概区间[a,b]
其中，a,b都是整数，找到i**2大于fc的i，然后break，这样可以确定所得根号值一定位于：[i-1,i]中：
对应的代码块如下所示，其中x是输入的待开根号的数字：
# 第一步，确定a，b区间
fc
 = math.ceil(x)

for
 i 
in
 range(
fc
 + 1):

if
 i ** 2 >= 
fc
:

break
    a, b = i - 1, i

print
(f
'确定的区间为[{a}-{b}]'
)

然后，第二步，二分法迭代。既然是迭代，就要确定迭代的终止条件，初始状态，状态转移。
其中，终止条件就是搜索的区间长度变得非常小，达到阈值，默认为0.000000001，终止迭代。
初始状态时，搜索区间为[a,b]，也就是上面第一步确定的区间。
状态转移基于二分法策略，既然是二分，也就是每迭代一次，区间长度减半。
那么问题来了，我们需要确定是选择左半区间还是选择右半区间，这个确定标准是关键。不过，在开根号这里，并不难想出来。如果我们选择左半区间，意味着解一定在区间[a,mid]中，这也就意味着：a带入到曲线中与mid带入到曲线中乘积为负值，其中曲线方程为：
# 第二步，二分法迭代
while
 abs(a - b) > precision:

        mid = (a + b) / 2

if
 (a ** 2 - x) * (mid ** 2 - x) < 0:

            b = mid

else
:

            a = mid

return
 a

完整代码

将上面的两步综合起来，完整代码如下所示：
import
 math



defmy_sqrt(x, precision=0.000000001):
if
 x < 
0
:

raise
 ValueError(
'x<0'
)


# 第一步，确定a，b区间
    fc = math.ceil(x)

for
 i 
in
 range(fc + 
1
):

if
 i ** 
2
 >= fc:

break
    a, b = i - 
1
, i

    print(
f'确定的区间为[{a}-{b}]'
)


# 第二步，二分法迭代
    i = 
1
while
 abs(a - b) > precision:

        mid = (a + b) / 
2
if
 (a ** 
2
 - x) * (mid ** 
2
 - x) < 
0
:

            b = mid

else
:

            a = mid

        print(
f'第{i}次迭代后sqrt({x})等于:{a}'
)

        i += 
1
return
 a



print(my_sqrt(
1.21
))


希望这篇文章对你现在或日后有帮助，欢迎点赞或收藏。
继续阅读
阅读原文