69. x 的平方根

1.题目描述

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:

示例 2:

2.思路

  一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt。可以利用二分查找在 0 ~ x 之间查找 sqrt。
  对于 x = 8，它的开方是 2.82842…，最后应该返回 2 而不是 3。在循环条件为 left <= right 并且循环退出时，right 总是比 left 小 1，也就是说 right = 2，left = 3，因此最后的返回值应该为 right 而不是 left 。

3.代码

class Solution {
public:
    int mySqrt(int x) {
       if(x <= 1){
           return x;
       }
       int left = 0,right = x;

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

4.复杂度分析

时间复杂度：O(logn)
空间复杂度：O(1)