LeetCode_69_x的平方根

题目描述：

二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为O(n)的数组，二分查找的时间复杂度为O(logn)

二分查找也可以看作双指针的一种特殊情况，但我们一般会将二者区分。双指针类型的题，指针通常是一步一步移动的，而在二分查找里，指针每次移动半个区间长度

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

示例：
输入: 4
输出: 2

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

解法1：二分查找

class Solution {
public:
    int mySqrt(int x) {

        if (x == 0) return 0;

        int l = 1,r = x,mid,sqrt;

        while (l <= r) {

            //求一串排列数的中间值的时候：最好用‘l + (r - l) / 2’ 
            //用‘(l + r) / 2’会很容易造成溢出
            //比如传入x = 2147483647的情况
            mid = l + (r - l) / 2;  
            sqrt = x / mid;

            if (sqrt == mid) return mid;
            else if (mid > sqrt) r = mid - 1;
            else l = mid + 1;
        }

        return r;
    }
};