69. Sqrt(x)

problem description

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

algorithm thought

第一次做这个题的时候，我也不是很清楚如何去计算一个数开根号。之后看了discuss了解到可以用二分查找。（感觉很多题都可以用二分查找，在一个大范围中找一个数，然后可以找到排除一半数的条件，条件很难找，需要仔细体会）。我记得我前几周做了一个contest也是用二分查找，当时做出来之后很惊讶。

回归题目本身，这里我们在0-x中查找是否有满足mid*mid=x的情况

code

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

algorithm analysis

二分查找，每次可以排除一半的数字。时间复杂度O(lgx)