leetCode-69:Sqrt(x)

问题描述

给定一个非负整数，要求在不使用编程语言自带的库函数的前提下找出这个整数的正数平方根（如果是小数，则向下取整）。题目链接：**点我**

样例输入输出

输入：4

输出：2

输入：8

输出：2

问题解法

一般情况下，求平方根可以使用 Math.sqrt 函数进行求解，但是题目已经明确要求不能使用库函数。那简单一点的做法就是遍历整数，判断其平方是否是小于等于目标树的最大整数，如果是，当前这个数字就是求解的答案。再优化点的做法是使用二分查找进行求解，从而将时间复杂度从 O(n) 降低到 O(log n) 。代码如下

class Solution {
    public int mySqrt(int x) {
        if (x < 2) {
            return x;
        }
        
        int start = 1;
        int end = x / 2;
        while (start <= end) {
            int middle = (start + end) / 2;
            if (x / middle >= middle) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }
        
        return start - 1;
    }
}