post on 07 May 2025 about 3466words require 12min
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
参考博客 代码随想录
使用二分法的前提条件
希望通过这道题目，大家会发现平时写二分法，为什么总写不好，就是因为对区间定义不清楚。
确定要查找的区间到底是左闭右开[left, right)，还是左闭又闭[left, right]，这就是不变量。
然后在二分查找的循环中，坚持循环不变量的原则，很多细节问题，自然会知道如何处理了。
解法一采用闭区间的二分
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0,right = nums.size()-1;
while(left <= right){
int mid = (left+right)/2;
if(nums[mid] == target)return mid;
if(nums[mid] < target)left = mid + 1;
if(nums[mid] > target)right = mid -1;
}
return -1;
}
};
解法二 采用左闭右开的区间进行二分
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0,right = nums.size();
while(left < right){
int mid = (left+right)/2;
if(nums[mid] == target)return mid;
if(nums[mid] < target)left = mid + 1;
if(nums[mid] > target)right = mid;
}
return -1;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
int searchInsert(vector<int> &nums, int target)
{
int left = 0, right = nums.size() - 1;
int mid = 0;
while (left <= right)
{
mid = (left + right) / 2;
if (nums[mid] < target)
{
left = mid + 1;
}
if (nums[mid] > target)
{
right = mid - 1;
}
if (nums[mid] == target)
return mid;
}
return left;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution
{
int lower_bound(vector<int> &nums, int target)
{
int left = 0, right = (int)nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] >= target)
right = mid - 1;
if (nums[mid] < target)
left = mid + 1;
}
return left;
}
public:
vector<int> searchRange(vector<int> &nums, int target)
{
int start = lower_bound(nums, target);
if (start == nums.size() || nums[start] != target)
return {-1, -1};
int end = lower_bound(nums, target + 1) - 1;
return {start, end};
}
};
参考博客
## 二分 ```cpp
class Solution { public: int mySqrt(int x) { int left = 0, right = x; while(left <=right){ long long mid = left + (right - left) / 2; if(mid * mid <= x){ left = mid + 1; } else{ right = mid - 1; } } return right; } };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
## 牛顿迭代法
```cpp
// f(x) = x^2 - C_
// f'(x) = 2x_
// f(x) = 0 的解为 x = sqrt(C)_
// f(x) ~= f(x0) + f'(x0)(x - x0)_
// 0 = x0^2 - C + 2x0(x - x0)_
// x = (C - x0^2) / 2x0 + x0 = (x0 + C / x0) / 2_
class Solution
{
public:
int mySqrt(int x)
{
if(x == 0)
return 0;
long x0 = x;
while(x0 * x0 > x){
x0 = (x0 + x / x0) / 2;
}
return (int)x0;
}
};
## 神奇的 0x5f3759df
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 使用快速平方根算法（Fast Inverse Square Root）的变体_
// 0x5f3759df 是一个魔法数字，用于快速估计平方根_
class Solution
{
public:
int mySqrt(int x)
{
// 使用 long 类型避免整数溢出_
long x0 = x;
// 使用魔法数字进行快速估计_
// x0>>1 相当于除以 2，用于快速估计_
x0 = 0x5f3759df - (x0>>1);
// 使用牛顿迭代法进行精确化_
// 迭代公式：x = (x + n/x) / 2_
while (x0 * x0 > x)
{
x0 = (x0 + x / x0) / 2;
}
return (int)x0;
}
};
## 位运算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
_// 使用位运算求解x的算术平方根_
int mySqrt(int x)
{
_ // m初始化为2^30，用于逐位检查_
unsigned m = 0x40000000, y = 0, b = 0;
while (m != 0)
{
_ // 计算当前位可能的平方值_
b = y | m;
_ // y右移一位，为下一位做准备_
y = y >> 1;
_ // 如果x大于等于当前平方值，说明该位可以取1_
if (x >= b)
{
_ // 更新x的值_
x = x - b;
_ // 将当前位设为1_
y = y | m;
}
_ // m右移两位，检查下一位_
m = m >> 2;
}
return y;
}
## 袖珍计算器(使用 exp 与 ln 函数进行求解)
使用$\sqrt{x} = e^{\frac{1}{2}lnx}$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cmath>
_// 使用数学公式求解 x 的算术平方根_
_// 利用公式：sqrt(x) = e^(0.5 * ln(x))_
class Solution
{
public:
int mySqrt(int x)
{
_ // 处理特殊情况：x 为 0 时直接返回 0_
if(x == 0)
return 0;
_ // 使用 exp 和 log 函数计算平方根_
_ // exp(0.5 * log(x)) = e^(0.5 * ln(x)) = sqrt(x)_
int res = exp(0.5 * log(x));
return (long long)(res + 1) * (res + 1) <= x ? res + 1 : res;
}
};
与前面的题非常相似
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
public:
bool isPerfectSquare(int num)
{
int left = 0, right = num;
while(left <= right){
long long mid = left + (right - left) / 2;
if(mid * mid == num)
return true;
else if(mid * mid < num)
left = mid + 1;
else
right = mid - 1;
}
return false;
}
};
Related posts