【算法笔记】二分算法原理的深度剖析
🔥个人主页：大白的编程日记
🔥专栏：算法笔记
文章目录
前言
哈喽，各位小伙伴大家好！上期我们讲了滑动窗口的算法原理。今天我们来讲二分查找算法。话不多说，我们进入正题！向大厂冲锋！
一.二分查找
1.1题目
- 题目：二分查找
1.2朴素二分
如果存在二段性我们就可以快速筛选掉一段不存在答案的区间
1.3细节问题
这里我们要注意循环结束条件和中点的查找。
在我们的朴素二分中中点取左端和右端都是可以的。
1.4代码实现
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;//偶数取左端，+1取右端
if(nums[mid]<target)
{
left=mid+1;
}
else if(nums[mid]>target)
{
right=mid-1;
}
else
{
return mid;
}
}
return -1;
}
};
1.5朴素模版总结
这就是我们的朴素二分模版。具体括号的具体内容结合题目填充即可。？
二.在排序数组中查找第一个和最后一个元素的位置
2.1题目
2.2思路分析
- 左端点
- 左端点细节问题
- 右端点
- 右端点细节问题
2.3代码实现
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;
int begin,end;
while(left<right)//找左端点
{
int mid=left+(right-left)/2;//取左端点
if(nums[mid]>=target)
{
right=mid;
}
else
{
left=mid+1;
}
}
if(nums[left]!=target)
{
return {-1,-1};
}
begin=left;
left=0,right=nums.size()-1;
while(left<right)//找右端点
{
int mid=left+(right-left+1)/2;//取右端点
if(nums[mid]<=target)
{
left=mid;
}
else
{
right=mid-1;
}
}
if(nums[left]!=target)
{
return {-1,-1};
}
end=right;
return {begin,end};
}
};
2.4左右端点二分模板总结
左端点
右端点
循环条件
left<right中点操作
三.搜索插入位置
3.1搜索插入位置
- 题目：搜索插入位置
3.2思路分析
我们只需要查找左端点即可。
3.3代码实现
- 右端点
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr)
{
int left=1,right=arr.size()-2;
while(left<right)
{
int mid=left+(right-left+1)/2;
if(arr[mid]>arr[mid-1])
{
left=mid;
}
else
{
right=mid-1;
}
}
return left;
}
};
- 左端点‘
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr)
{
int left=1,right=arr.size()-2;
while(left<right)
{
int mid=left+(right-left)/2;
if(arr[mid]<arr[mid+1])
{
left=mid+1;
}
else
{
right=mid;
}
}
return left;
}
};
四.寻找峰值
4.1题目
- 题目：寻找峰值
4.2思路分析
4.3代码实现
class Solution {
public:
int findPeakElement(vector<int>& nums)
{
int left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<nums[mid+1])
{
left=mid+1;
}
else
{
right=mid;
}
}
return left;
}
};
五.寻找旋转数组中的最小值
5.1题目
- 题目：寻找旋转数组中的最小值
5.2思路分析
5.3代码实现
- num[0]
class Solution {
public:
int findMin(vector<int>& nums)
{
int left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<nums[0])
{
right=mid;
}
else
{
left=mid+1;
}
}
return nums[left]>nums[0]?nums[0]:nums[left];//特殊处理
}
};
- num[n]
class Solution {
public:
int findMin(vector<int>& nums)
{
int left=0,right=nums.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(nums[mid]<nums[nums.size()-1])
{
right=mid;
}
else
{
left=mid+1;
}
}
return nums[left];
}
};
后言
这就是二分算法的深度剖析。二分算法细节还是挺多的。大家自己好好梳理一下。今天就分享到这，感谢各位的耐心垂阅！咱们下期见！拜拜~
