NC32 求平方根

题目链接：https://www.nowcoder.com/practice/09fbfb16140b40499951f55113f2166c

题目描述

实现函数 int sqrt(int x).

计算并返回 x 的平方根（向下取整）

数据范围： 0 <= x < 2^31−1

要求：空间复杂度 O(1)，时间复杂度 O(logx)

示例 1：

输入：2
返回值：1

示例 2：

输入：2143195649
返回值：46294

解题代码

import java.util.*;


public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int sqrt (int x) {
        // write code here
        // x不能为0
        if (x <= 0) {
            return 0;
        }
        int res = x;
        // 利用牛顿迭代式进行求解
        while (res > x / res) {
            res = (res + x / res) / 2;
        }
        return res;
    }
}