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;
            }
        }
    }
}