LeetCode:Sqrt(x)

Sqrt(x)
Total Accepted: 94989 
Total Submissions: 373552 
Difficulty: Medium
Implement  int sqrt(int x) .
Compute and return the square root of x.
Subscribe to see which companies asked this question
Hide Tags
 
Binary Search Math
Hide Similar Problems
 
(M) Pow(x, n)
考え方:二分検索.
例:x=10
1 2 3 4 5 6 7 8 9 10
設定:left=1、right=10、mid=(1+10)/2=5
mid*mid>x*xのためright=mid;この場合、left=1、right=5、mid=(1+5)/2=3;
mid*mid<=x*xのためleft=mid;このときleft=3,right=5,mid=(3+5)/2=4;
mid*mid>x*xのためright=mid;このときleft=3,right=4,mid=(3+4)/2=3である.
left+1==right,break;
結果を返します:left=3;
c++ code:

class Solution {
public:
    int mySqrt(int x) {
        if(x <= 1) return x;
        
        int left = 1,right = x;
        
        while(left + 1 < right) {
            int mid = left + (right-left)/2;
            if(mid <= x/mid)
                left = mid;
            else
                right = mid;
        }
        return left;
    }
};