各位小伙伴们，好久不见，前段时间由于博主个人原因，导致文章停更，那么从今日起算法系列的文章将恢复更新。
闲话少叙，我们直接进入正题！！！
目录
算法文章之二分算法系列
第一题
题目链接
题目展示
代码原理
二分查找
那么这里一定有小伙伴会疑惑，为什么就能使用二分了呀，晕。打住，别晕哈，为什么就能使用二分以及二分的使用条件是什么，我们在文章末尾会细讲。
代码编写
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) + 1 / 2;
if(nums[mid] < target)
left = mid + 1;
else if(nums[mid] > target)
right = mid - 1;
else
return mid;
}
return -1;
}
};
第二题
题目链接
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
题目展示
代码原理
查找左端点
查找右端点
这里的获得方式与前面左端的查找方式一样的，但结论是相反的，这里就不再叙述
代码编写
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.size() == 0)
return {-1, -1};
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[right] != target)
return {-1,-1};
int begin = right;
right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(nums[mid] <= target)
left = mid;
else
right = mid - 1;
}
int end = right;
return {begin, end};
}
};
总结
通用技巧
1.
2.遇到这种要求左右两个端点的一般求出左端点后，右端点的条件直接取反即可
第三题
题目链接
题目展示
代码原理
代码编写
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 left + 1;
return left;
}
};
好的，那么本篇文章的算法内容就讲这么多，那么剩下内容就来讲讲为什么这些题能用二分算法以及使用条件是什么
为什么这三题也可以使用二分
朴素二分的核心思想
先整两个指针（l和r),求出中间值，然后与目标值进行比较，最后再分情况讨论
非朴素二分可以使用的原因
设target = 3
那么此时mid指针会从区间[left,mid]中进行查找，如果没找到又会跑去区间[mid,right]中查找，因此它的时间复杂度会在极端情况下会降，从而失去了二分的特性
二分的使用条件
在目标值的两侧是否存在二段性，即目标值的一侧小于目标值，另一侧大于目标值
那么本篇文章的内容就先到这里，我们下期文章再见！！！
记得一键三联哦！！！
