2025-05-07-二分查找
参考博客
代码随想录
使用二分法的前提条件
- 元素有序且不重复
希望通过这道题目，大家会发现平时写二分法，为什么总写不好，就是因为对区间定义不清楚。
确定要查找的区间到底是左闭右开[left, right)，还是左闭又闭[left, right]，这就是不变量。
然后在二分查找的循环中，坚持循环不变量的原则，很多细节问题，自然会知道如何处理了。
704. 二分查找 - 力扣（LeetCode）
解法一采用闭区间的二分
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;
}
};解法二 采用左闭右开的区间进行二分
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;
}
};35. 搜索插入位置 - 力扣（LeetCode）
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;
}
};34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
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};
}
};69. x 的平方根 - 力扣（LeetCode）
参考博客
二分
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;
}
};牛顿迭代法
// 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
// 使用快速平方根算法（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;
}
};
位运算
// 使用位运算求解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 函数进行求解)
使用
#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;
}
};
367. 有效的完全平方数 - 力扣（LeetCode）
与前面的题非常相似
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;
}
};
