这道题目就是说，不要用任何自带的exponent function or operator， 求这个平方根。如果结果非整数，则向下取整。x非负整数。
solution: binary search
这里看到了一些很好的总结：
“具体到代码上，二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以，因此
有些初学者会容易搞不清楚如何定义区间开闭性。这里我提供两个小诀窍，第一是尝试熟练使用
一种写法，比如左闭右开(满足 C++、Python 等语言的习惯)或左闭右闭(便于处理边界条件)，
尽量只保持这一种写法;第二是在刷题时思考如果最后区间只剩下一个数或者两个数，自己的写
法是否会陷入死循环，如果某种写法无法跳出死循环，则考虑尝试另一种写法。
”------leetcode 101 （这本书真的很不错，感谢作者大大）
“because you are taking the the smaller number among left and right, since you need to round down the number if it is not happen to be pivot. Essentially you are rounding down the number. And since the loop has condition left <= right, that means outside the loop, right is the smaller number, which is the one that you are rounding down to.” -- by one author in leetcode. about why we take the right number.
my solution:
class Solution {
public int mySqrt(int x) {
if(x<=1) return x;
int start = 2, end =x;
while(start <= end) {
int mid = start + (end - start) / 2;
int sqrt = x / mid;
if(sqrt == mid) {
return mid;
} else if (sqrt > mid) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return end;
}
}
time complexity: O(logn) n is x
space complexity: O(1)
