LeetCode | Sqrt(x)

题目

Implement int sqrt(int x).

Compute and return the square root of x.

两种方法：

1. 牛顿法（解法1）

2. 二分查找（解法2）

解法1

public class Sqrt {
	public int sqrt(int x) {
		double ret = 1, temp = 0;
		while ((int) ret - (int) temp != 0) {
			temp = ret;
			ret = ret / 2 + (double) x / (2 * ret);
		}
		return (int) ret;
	}
}

public class Sqrt {
	public int sqrt(int x) {
		if (x < 2) {
			return x;
		}
		int left = 1;
		int right = x;
		while (left + 1 < right) {
			int mid = left + (right - left) / 2;
			int result = x / mid;
			if (result > mid) {
				left = mid;
			} else if (result < mid) {
				right = mid;
			} else {
				return mid;
			}
		}
		return left;
	}
}