【优选算法】Binary-Blade：二分查找的算法刃（上）
文章目录
- 1.概念解析
- 2.二分查找的简单模版
- 3.二分查找的进阶模版
- 4.x的平方根
- 5.搜索插入位置
- 希望读者们多多三连支持
- 小编会继续更新
- 你们的鼓励就是我前进的动力！
本篇是优选算法之二分查找算法，该算法是一种高效的在有序数组中查找特定元素的搜索算法
1.概念解析
🚩什么是二分查找算法？
每次比较中间元素，通过判断中间元素与目标元素的大小关系，将搜索区间缩小一半，持续这个过程，直至找到目标元素或者确定目标元素不存在
2.二分查找的简单模版
✏️题目描述：
✏️示例：
传送门：二分查找
题解:
在一个无论是有序还是无序的数列里，一般最先想到的就是暴力解法遍历一遍，然后符合条件则成立，这种方法固然是好用，但是一般在搜索数据的过程中，数据量庞大，O(n)的时间复杂度还是太大了，那么这时候就要使用时间复杂度为O(log n)的二分查找
💻第一步：
二分查找说的就是折中查找，那么二段性就是重要的第一步，找出左右区间不同的地方
比如这题就是 target 的左区间小于它，右区间大于它，根据这个特性不断调整left和right的位置，接下来看一下具体实现
💻第二步：
不断循环算出mid的值，与target作比较，如果大于target，说明mid所指位置及后面的数都不是符合target的数，right = mid - 1；如果小于target，说明mid所指位置及前面的数都不是符合target的数， left = mid + 1
💻细节问题：
🚩循环条件
循环条件为 left<=right ，因为当 left 变得比 right 大时，查找区间自然就不存在了；如果只是 left < right，会遗漏掉最后一个元素。例如，在数组只有一个元素时，初始left = 0，right = 0， 若条件是 left < right，循环压根不会进入，直接判定未找到，但实际上这个唯一元素还没检查，使用 left <= right 就能保证这种单元素数组也能被正确查找
🚩时间复杂度
不断将区间折中，最终折中为区间长度为1即找到指定元素，即 n /
2
x
2^x
2x = 1，解得 x =
log
n
\log_n
logn
假设要查找2³²个数中的一个数，暴力解法就是有多少数就找多少次，而二分查找是指数关系，只需要找32次，明显效率高了不止一点
💻代码实现：
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
int search(vector<int>& nums, int target)
{
int left = 0, right = nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] > target)
{
right = mid - 1;
}
else if (nums[mid] < target)
{
left = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
};
3.二分查找的进阶模版
✏️题目描述：
✏️示例：
传送门：二分查找的进阶模版
题解:
题目中的非递减的意思就是数据要么递增要么不变
💻第一步：
如果用简单的二分查找方法必然是不行的，因为不知道找到的数是否为端点值，因此在此基础上衍生出查找左右端点的进阶二分查找
先找左端点，主要的思路还是一样，找出二段性，那么为什么是像如图分类呢？我们要找的是左端点等于target的情况，那么应该在左端点和前一个数之间划分，那么在右区间寻找的时候就会有等于target
在左区间寻找，mid所指位置及前面的数都不是符合target的数，即使指向左端点前一个数，也是要越过该数，指向左端点，即left = mid + 1；在右区间寻找，mid所指的位置可能是左端点值，所以不能越过左端点，即right = mid
💻第二步：
接着寻找右端点也是同理
我们要找的是右端点等于target的情况，那么应该在右端点和后一个数之间划分，那么在左区间寻找的时候就会有等于target
在右区间寻找，mid所指位置及后面的数都不是符合target的数，即使指向右端点后一个数，也是要越过该数，指向右端点，即right = mid - 1；在左区间寻找，mid所指的位置可能是右端点值，所以不能越过右端点，即left = mid
💻细节问题：
🚩循环条件
无论是找左端点还是右端点，有right = mid和left = mid，通过举例会发现，当left和right汇合到一个数时，因为这两种情况会一直停在那儿不动，会死循环
🚩求mid操作
求mid的公式是否加1其实是对偶数个数字的简单模版时候是没区别的，无非是先求右边还是先求左边的区别。但是在如图进阶二分模版极端条件下，求左端点，只有两个数时，如果用加1的公式的话，mid会指向右边，由于right = mid，right就会一直不动死循环
右端点也是同理，在如图进阶二分模版极端条件下，求右端点，只有两个数时，如果用不加1的公式的话，mid会指向左边，由于left = mid，right就会一直不动死循环
💻代码实现：
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
vector<int> searchRange(vector<int>& nums, int target)
{
vector<int> ret;
if (nums.size() == 0)
{
return ret = { -1,-1 };
}
int begin = 0, end = 0;
int left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target)
{
left = mid + 1;
}
else
{
right = mid;
}
}
if (nums[left] != target)
{
return ret = { -1,-1 };
}
else
{
begin = left;
}
left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + (right - left + 1) / 2;
if (nums[mid] > target)
{
right = mid - 1;
}
else
{
left = mid;
}
}
end = right;
return ret = { begin,end };
}
};
4.x的平方根
✏️题目描述：
✏️示例：
传送门：x的平方根
题解:
💻细节问题：
学习完模版后二分基本上都很简单，一般都是用进阶模版，确定二段性很重要
由于求平方根是向下取整，所以把等于的情况划分到左区间
💻代码实现：
#include <iostream>
using namespace std;
class Solution
{
public:
int mySqrt(int x)
{
if (x < 1)
{
return 0;
}
long long left = 0, right = x;
while (left < right)
{
long long mid = left + (right - left + 1) / 2;
if (mid * mid <= x)
{
left = mid;
}
else
{
right = mid - 1;
}
}
return left;
}
};
5.搜索插入位置
✏️题目描述：
✏️示例：
传送门：搜索插入位置
题解:
💻细节问题：
由于是在target大一位的数插入，所以把等于的情况划分到右区间
💻代码实现：
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
int searchInsert(vector<int>& nums, int target)
{
int left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target)
{
left = mid + 1;
}
else
{
right = mid;
}
}
if (nums[left] < target)
{
return right + 1;
}
return right;
}
};
🌸 愿新年如初春的花开般灿烂，芬芳四溢，盈满心间；
✨ 告别2024年的些许遗憾，迎接2025年的满怀希望；
🌟 愿你在新的一年里，心怀星光，步履坚定；
🎉 愿每一份努力都有收获，每一个梦想都能成真；
❤️ 愿日子如诗，岁月如歌，温柔且浪漫；
🌿 每一步都走得从容，每一天都活得明媚；
🎀 愿你在新岁中，遇见更闪亮的自己；
2025，期待你的美好与光芒！
各位2025新年快乐！
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
