题目描述

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.

思路

看到此题目的直觉想法就是使用牛顿迭代法求某个数的平方,关键思想就是使用直线逼近曲线。具体公式：Xn+1 = Xn - f(x)/f(x)'。做完之后，此题目在leetCode上是的标签是二分查找。若要使用二分查找，根据题目意思，low为1，high值最大为x/2+1，后面的思路就是直接借用二分查找算法的思想解题即可。

代码

  • 牛顿法解题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * using Newton'Method to implement sqrt 
 * @param x
 * @return
 */
public int mySqrtByNT(int x) {
 if (x <= 0) {
   	 return x;
    }
 double diff = 1e-9;
 double guess = 1.0;
 while (Math.abs((guess * guess - x))  > diff) {
	 guess = (guess + x / guess) / 2.0;
 }
 return (int)guess;
}
  • 二分查找法解题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
	 * using binary search to implement sqrt 
	 * @param x
	 * @return
	 */
	 public int mySqrtByBinarySearch(int x) {
		 if (x <= 0) {
	    	 return x;
	     }
	     if (x < 4) {
	    	 return 1;
	     }
	     int lo = 1;
	     int hi = x / 2 + 1;
	     while (lo <= hi) {
	    	 int mid = lo + (hi - lo) / 2;
	    	 int tmp = x / mid;
	    	 if (tmp == mid) {
	    		 return mid;
	    	 } else if (tmp > mid) {
	    		 lo = mid + 1;
	    	 } else {
	    		 hi = mid - 1;
	    	 }
	     }
	     return hi;
	 }