本篇文章我们继续学习c++算法
目录
第一题
题目链接
题目展示
代码原理
暴力解法
二分解法
代码编写
第二题
题目链接
题目展示
代码原理
代码编写
重点回顾
朴素二分
非朴素二分
重点一
重点二
重点三
第一题
题目链接
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
题目展示
代码原理
图1
从图1中我们将4567分为一组，012分为另一组，并且以2为参照点，从而有了图1中类似数学中的分段函数的图，从这个图中我们可以看到有明显的二段性，因此，我们就可以使用二分查找进行解题。那么在讲解二分算法之前，我们先来讲解一下这个暴力解法
暴力解法
依次遍历，最后取得最小值并返回即可
二分解法
代码编写
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
int x = nums[right];
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] > x)
left = mid + 1;
else
right = mid;
}
return nums[right];
}
};
第二题
题目链接
LCR 173. 点名 - 力扣（LeetCode）
题目展示
代码原理
代码编写
class Solution {
public:
int takeAttendance(vector<int>& records) {
int left = 0,right = records.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(records[mid] == mid)
left = mid + 1;
else
right = mid;
}
return records[left] == left? left + 1: left;
}
};
总结
其实从这道题中，我们可以发现这题的二段性并不是和之前一样是大小关系了，而是等于下标和不等于下标的关系了，因此我们在学习的时候不能把一个知识点学死了，随机应变才是上策
那么二分查找的到这里就已经结束了，我们最后再来回顾一下二分查找的重点
重点回顾
朴素二分
先根据最初的left和right指针计算出mid指针，再将[mid]与目标值进行比较，然后缩小空间，继续查找
非朴素二分
重点一
循环条件必须是left < right,至于为什么只能是它，前面的文章已经讲解原因如果已经忘记的小伙伴可以返回前面的文章仔细阅读，如果是新来的小伙伴，那么先当作一个结论记下来，把题目大概理解后再回去看原因
重点二
求重点的操作，注意了这个必须得记住
重点三
当推理出左端点的条件后，右端点的条件取反即可
重点四
二分算法的使用前提是有二段性
那么本篇文章的内容就先到这里了，我们下期文章再见！！！
记得一键三联哦！！！
)
