面试算法72：求平方根
题目
输入一个非负整数，请计算它的平方根。正数的平方根有两个，只输出其中的正数平方根。如果平方根不是整数，那么只需要输出它的整数部分。例如，如果输入4则输出2；如果输入18则输出4。
分析
整数n的平方根一定小于或等于n。同时，除0之外的所有整数的平方根都大于或等于1。因此，整数n的平方根一定在从1到n的范围内，取这个范围内的中间数字m，并判断m2是否小于或等于n。如果m2≤n，那么接着判断(m+1)2是否大于n。如果满足(m+1)2>n，那么m就是n的平方根。
解
public class Test {public static void main(String[] args) {System.out.println(mySqrt(18));}public static int mySqrt(int n) {int left = 1;int right = n;while (left <= right) {int mid = left + (right - left) / 2;if (mid <= n / mid) {if ((mid + 1) > n / (mid + 1)) {return mid;}left = mid + 1;}else {right = mid - 1;}}return 0;}
}