代码测试: 求整数平方根

Programming
1

代码测试的问题去哪里问?

x是正整数

def find_square_root(x):
    lo = 0
    hi = x

    while lo < hi:
        mid = (lo + hi) // 2 #

        if mid ** 2 == x:
            lo = mid
            return lo
        if mid ** 2 < x:
            lo = mid + 1
        if mid ** 2 > x:
            hi = mid
        print(f"mid={mid}, lo={lo}, hi={hi}")

    return lo - 1

测试

In [5]: find_square_root(10) 
mid=5, lo=0, hi=5
mid=2, lo=3, hi=5
mid=4, lo=3, hi=4
mid=3, lo=4, hi=4
Out[5]: 3

In [6]: find_square_root(80) 
mid=40, lo=0, hi=40
mid=20, lo=0, hi=20
mid=10, lo=0, hi=10
mid=5, lo=6, hi=10
mid=8, lo=9, hi=10
mid=9, lo=9, hi=9
Out[6]: 8

这个解法有问题, 但找不到那个edge case.

退出条件是 lo == hi

当最后剩下两个相邻的数值, lo, hi
mid = (lo + hi) // 2, 因为是floor div, mid = lo;
当mid ** 2 < x, hi = mid = lo,
这种情况下没有问题, 因为lo被测试了.

但是当 mi**2 > x; lo = mid + 1, 在lo = hi = mid +1的时候, hi 这个点位没有被测试,.

找不到这样一个值, 求助.

2 
>>> find_sq_r(1)
mid=0, lo=1, hi=1
0
>>> find_sq_r(0)
-1

Chez Scheme Version 9.5.2
Copyright 1984-2019 Cisco Systems, Inc.

> (sqrt 1)
1
> (sqrt 0)
0
> (sqrt 4)
2
1 个赞
3

恩, 测试了很多没找出来.

加上一个base case ,

if i < 2: return i

就好了?

我感觉是问题里描述的bug.

4

这个修改对你的问题是对的. 但是原因略复杂.

这个二分法并不正确. 一个是没有校验初始 lo >= hi 的情形, 另一个是在 lo = mid = hi - 1 的情况下, 如果 mid ** 2 < x, 那么 lo = mid + 1 = hi, 这时候退出循环, 实际上并没有检查 hi**2.

分别对应着 LdBeth 给出的两种情况.

由于你初始选取的 hi = x, 非负整数里除了0, 1 之外, 均有 hi**2 > x; 二分法进行过程中也确保了 hi**2 > x, 所以上面说的两种情况不会出现.

1 个赞
5

应该是有问题, 但是过了亿次测试.

for i in range(50, 50**2):
     res = find_square_root(i**i)
     assert res == i, f"res={res}, i={i}"
6

非负整数里除了 0, 1 之外, 已经由初始条件确保了 hi**2 > x 一直成立直到终了.

7

弄清楚了，解法没问题，推理有漏洞。 hi值也测试过了，因为hi = mid, 在前面测试过了。

8

论 mathematical induction 的重要性