Implementint sqrt(int x).

Compute and return the square root ofx.

求一个数的平方根。

解法：二分法，迭代循环在x范围内找中间值mid，然后判断mid * mid和x，如果mid > x/mid（不要写成middle*middle==x，会溢出），说明这个数大了，就保留左边，right = mid -1。否则保留右边, left = mid + 1。直到left > right结束循环，返回left - 1。因为当x>2时，x/2的平方一定大于x，不可能是平方根，右指针可以从x/2开始。

Java:

public class Solution {    
    public int sqrt(int x) {    
        if(x<=1) {    
            return x;    
        }    
            
        int begin = 1;    
        int end = x;    
        int middle = 0;    
        while(begin<=end) {    
            mid = begin + (end - begin)/2;     
            if(middle == x/mid) {    
                return mid;    
            } else {    
                if (middle < x/mid) {    
                    begin = mid + 1;    
                } else {    
                    end = mid - 1;    
                }    
            }    
                
        }       
        return end;    
    }    
} 　

Python:

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 2:
            return x
        
        left, right = 1, x // 2
        while left <= right:
            mid = left + (right - left) // 2
            if mid > x / mid:
                right = mid - 1
            else:
                left = mid + 1

        return left - 1

C++:

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;
            if (x / mid >= mid) left = mid + 1;
            else right = mid;
        }
        return right - 1;
    }
};

类似题目：

[LeetCode] 50. Pow(x, n) 求x的n次方

All LeetCode Questions List 题目汇总