首页 > 代码库 > Sqrt(x)
Sqrt(x)
Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
分析：
方案一：遍历0~n， 第一次出现 i * i > n，返回 i-1即可。
方案二：
二分搜索：
（1） 当n = 0, 或者 n = 1时，返回 n
（2） 初始化 s = 0, e = n; //注意e的取值不能超过INT_MAX的开方值，即e不大于46341，否则 mid * mid 值有可能会溢出，导致计算结果出错。
（3） 当 s < e 时，mid = (s + e)/2;
当mid * mid < n时， s = mid;
当mid * mid > n时， e = mid;
当mid * mid = n时，return mid.
当s + 1 = e时，说明s * s < n < (s + 1) * (s + 1)， 即 s为所求值。否则，继续执行该循环。
1 class Solution 2 { 3 public: 4 int sqrt(int n) 5 { 6 int m = n; 7 if(n == 0 || n == 1) 8 return n; 9 10 int s = 0, e = n, mid = 0;11 if(e > 46341)12 e = 46341;13 14 while(s < e)15 {16 mid = (s + e)/ 2;17 if(mid * mid < n)18 s = mid;19 else if(mid * mid > n)20 e = mid;21 else22 return mid;23 24 if(s + 1 == e)25 return s;26 }27 }28 };
Sqrt(x)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。