二分大法| 求X的开方，结果一个公式解决！ (力扣69.X 的平方根)

本文将讲述：69.X 的平方根(简单）

题目：给你一个非负整数，求其开方，向下取整

思路：

首先，我们把问题数学表示出来，就是：求 f(x) = x^2 - a = 0的解；

而且，题目要求的是 非负整数，所以 我们只需要考虑 x >= 0 的情况

我们可以注意到：f(0) <= 0 ; f(a) >=0

(好家伙，其实这又是一道数学题！)

所以，由零点定理

我们可以在 区间 [0，a] 上，找到我们想要的解了！

在区间上，首先想到的是二分法在区间查找~

class Solution {// 想象成 f(x) = x^2 - a = 0 的解// 非负整数 所以在 [0,a] 区间可以找到解// 1.使用二分法public:int mySqrt(int a) {if (a == 0) return 0;int left = 1;int right = a;int mid,sqrt;while (left <= right) {mid = left + ( right - left) / 2;sqrt = a / mid ;if (sqrt == mid) {return mid;} else if (mid > sqrt) {right = mid - left;} else {right = mid + 1;}}return right;} };

结果，好家伙~ 超时了！

后面看到一种解法，纯数学~

一个公式就解决了！

那就是 牛顿迭代公式

class Solution {// 2.牛顿迭代法 public:int mySqrt(int a) {long x = a;while (x*x > a) {x = (x + a / x) / 2;}return x;} };

总结

以上是生活随笔为你收集整理的二分大法| 求X的开方，结果一个公式解决！ (力扣69.X 的平方根)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。