69 Sqrt(x)

LeetCode

Given a non-negative integer x, compute and return the square root of x.

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

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2

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

假设 sqrt(x) = a ，当 x 不少于 1 时，a 满足 x/a>=a ，当等号成立时可以直接返回。等号不成立时，可能 a 也为正确答案，此时左指针会指向 a+1 ，右指针不断向左移动，直到右指针为 a 时跳出循环，此时右指针为正确答案。

两个指针，使用二分查找。时间复杂度 o(log n) 。

public int mySqrt(int x) {
    if(x<=1) return x;
    int low=0,high=x;
    int mid,num;
    while(low<=high){
        mid = (low+high)/2;
        num=x/mid;
        if(num<mid){
            high = mid-1;
        } else if(num > mid){
            low = mid+1;
        } else {
            return mid;
        }
    }
    return high;
}