69. Sqrt(x).md

69. Sqrt(x)

Question:

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.

Thinking:

• Method:
  • 可能性就是在1 - x之间，通过二分法查找出准确值。

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

二刷

二刷的时候还是参考了一刷的答案，实际上没有想到用二分法来做这道题。而且有个很有趣的现象，如果使用乘法来判断大小则无法AC，如果我们使用除法则可以做到AC。

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

Third Time

• Method 1: binary search

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