二分查找
- 二分查找也常被称为二分法或者折半查找，每次查找时通过将待查找区间分成两部分并只取 一部分继续查找，将查找的复杂度大大减少。对于一个长度为 $O(n)$ 的数组，二分查找的时间复 杂度为 $O(log n)$
- 数学定义: 给定一个在
[a, b]区间内的单调函数 $f(x)$ ，若
$f(a)$ 和 $f(b)$ 正负性相反，那么必定存在一个解 $c$ ，使得 $f(c) = 0$
[69] x 的平方根
https://leetcode-cn.com/problems/sqrtx/description/
- algorithms
- Easy (39.23%)
- Likes: 632
- Dislikes: -
- Total Accepted: 280.6K
- Total Submissions: 715.3K
- Testcase Example: ‘4’
- Source Code: 69.sqrtx.cpp
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4 输出: 2
示例 2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
方法1: 二分查找
思路: 设置两个指针, 代表区间 [a, b] 的首尾(注意这里双指针算法不太同, 双指针是一次移动一位, 这里一次移动半个区间) , 取中位数 mid 与 x/mid 进行计算对比, 若 mid 大, 则取 mid 左边区间继续计算, 反之则取右边区间
class Solution {
public:
int mySqrt(int x) {
if(x==0) return x;
int left=1, right=x, mid=0, sqrt=0;
while(left <= right){
mid = (right - left) / 2 + left;
// cout << mid << endl;
sqrt = x / mid;
if(sqrt == mid){
return mid;
}else if(sqrt > mid){
left = mid + 1;
}else{
right = mid - 1;
}
}
return right;
}
};
复杂度分析:
- 时间复杂度:
O(logn) - 空间复杂度:
O(1)
方法2: 牛顿迭代法
也就比第一种方法快 亿 点点
牛顿迭代 原理
待完善
迭代公式: $x_{n+1} = x_n - f(x_n) / f’(x_n)$
求平方根, 等价于给定 $f(x) = x^2 - a = 0$, 代入上式, 可🉐️迭代公式: $x_{n+1} = (x_n + a / x_n) / 2$
class Solution {
public:
int mySqrt(int x) {
long n = x;
while( n * n > x ){
n = (n + x / n) / 2;
}
return n;
}
};
