Implement int sqrt(int x). Compute(计算) and return the square root of x.
思路：用二分查找搜寻其平方根，若其平方根不为整数，则要找到最后一个平方小于该值的数作为答案。
public class Sqrt_x { public static int mySqrt(int x) { if(x<0) return -1; if(x<2) return x; long start=0; long end=x/2+1; long result=0; while(end>=start) { result=(start+end)/2; if(result*result==x) return (int)result; if(result*result>x) end=result-1; else start=result+1; } //找到最后一个平方小于该值的数作为答案 while(result*result>x) { result--; } return (int)result; } public static void main(String[] args) { int x=17; System.out.println(mySqrt(x)); } }
