求平方根

题目：

实现函数 int sqrt(int x).

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

示例：

输入：2

返回值：1

输入：2143195649

返回值：46294

解题思路：

二分法：

我们先定义左右边界left、right，通过二分法找到mid值，检验mid * mid是否等于x，如果小于x，则让left=mid+1;如果大于x，则让right=mid-1；直到找到mid * mid=x,循环结束。

代码示例：

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param x int整型 
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int Sqrt(int x ) {
    // write code here
    long left = 0,right = x;
    while(left <= right){
        long mid = left + ((right - left)/2);
        if(mid*mid <= x && (mid+1)*(mid+1) > x)
           return (int)mid;
        else if(mid*mid < x) 
            left = mid + 1;
        else right = mid - 1;
        }
        return -1;
}