leetcode:69. x 的平方根

题目:

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

分析:

简单

代码:

	public int mySqrt(int x) {
		if (x == 0)
			return 0;
		int end = x / 2 + 1;
		int start = 0;
		int mid = 0;
		while (end > start) {
			mid = (end + start + 1) / 2;
			if (x / mid == mid) {
				return mid;
			} else if (x / mid < mid) {
				if (x / (mid - 1) > mid - 1) {
					return mid - 1;
				}
				end = mid;
			} else {
				start = mid;
			}
		}
		return mid;
	}

效率:

总结:

简单