版權聲明:轉載請聯系本人,感謝配合!本站位址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50811232
翻譯
實作int sqrt(int x)。
計算并傳回x的平方根。
原文
Implement int sqrt(int x).
Compute and return the square root of x.
分析
首先給大家推薦維基百科:
zh.wikipedia.org/wiki/二進制搜尋樹 en.wikipedia.org/wiki/Binary_search_tree大家也可以看看類似的一道題:
LeetCode 50 Pow(x, n)(Math、Binary Search)(*)然後我就直接貼代碼了……
代碼
class Solution {
public:
int mySqrtHelper(int x, int left, int right) {
if (x == 0) return 0;
if (x == 1) return 1;
int mid = left + (right - left) / 2;
if (mid > x / mid) right = mid;
if (mid <= x / mid)left = mid;
if (right - left <= 1) return left;
else mySqrtHelper(x, left, right);
}
int mySqrt(int x) {
return mySqrtHelper(x, 0, x);
}
};