二分查找求x的平方根

以下是基于二分查找实现求整数平方根的Python代码：

x = int(input('please input a int:'))

if x < 0:
    print('Error: x must be a non-negative integer.')
elif x == 0:
    print(0)
else:
    low, high = 1, x
    while low <= high:
        mid = (low + high) // 2
        if mid * mid <= x < (mid + 1) * (mid + 1):
            print(mid)
            break
        elif mid * mid > x:
            high = mid - 1
        else:
            low = mid + 1

该算法的思路是：在区间[1, x]中进行二分查找，每次取中间值mid，判断mid的平方是否等于x，如果是，则mid即为所求；如果mid的平方小于x，则在[mid+1, x]中继续查找；如果mid的平方大于x，则在[1, mid-1]中继续查找。直到找到mid或者low>high时，算法结束。

相关问题

Java二分查找求平方根

以下是Java二分查找求平方根的代码实现：

public static double sqrt(int x) {
    if (x == 0) {
        return 0;
    }
    double left = 1, right = x;
    while (left <= right) {
        double mid = left + (right - left) / 2;
        if (mid > x / mid) {
            right = mid - 1;
        } else {
            if ((mid + 1) > x / (mid + 1)) {
                return mid;
            }
            left = mid + 1;
        }
    }
    return -1;
}

该方法的思路是利用二分查找的思想，不断缩小平方根的范围，最终得到平方根的值。具体实现过程如下：

1. 如果x等于0，则直接返回0。

2. 定义左右边界，初始值分别为1和x。

3. 当左边界小于等于右边界时，进行循环。

4. 计算中间值mid，如果mid的平方大于x，则将右边界缩小到mid-1；否则，如果mid+1的平方大于x，则mid就是平方根，返回mid；否则，将左边界扩大到mid+1。

5. 如果循环结束仍未找到平方根，则返回-1。

D. DS查找——折半查找求平方根

折半查找又称二分查找，可以用来求解平方根。具体步骤如下：

1. 初始化左右边界，即左边界 l=0，右边界 r=x。

2. 进入循环，每次将中点 mid=(l+r)/2 计算出来。

3. 如果 mid 的平方等于 x，则直接返回 mid。

4. 如果 mid 的平方小于 x，则说明平方根在右半边，将左边界 l=mid。

5. 如果 mid 的平方大于 x，则说明平方根在左半边，将右边界 r=mid。

6. 直到左边界 l 和右边界 r 相遇，此时的 mid 就是平方根的整数部分，返回 mid 即可。

代码示例：

int mySqrt(int x) {
    if (x == 0) return 0;
    int l = 1, r = x;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {  // 判断 mid 是否为平方根
            return mid;
        } else if (mid > x / mid) {  // 平方根在左半边
            r = mid - 1;
        } else {  // 平方根在右半边
            l = mid + 1;
        }
    }
    return -1;  // 如果没有找到平方根，返回 -1
}

需要注意的是，为了防止 mid*mid 溢出，上面的代码判断 mid 是否为平方根时使用了 mid<=x/mid && (mid+1)>x/(mid+1) 的方式，而不是 mid*mid==x。另外，当 x==0 时，直接返回 0。