《算法题讲解指南：优选算法-二分查找》--23.寻找旋转排序数组中的最小值，24.0~n-1中缺失的数字
🔥小叶-duck：个人主页
❄️个人专栏：《Data-Structure-Learning》
《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心
✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游
目录
23.寻找旋转排序数组中的最小值
题目链接：
153. 寻找旋转排序数组中的最小值 - 力扣
题目描述：
题目示例：
解法（二分查找）：
算法思路：
题目中的数组规则如下图所示：
其中 C 点就是我们要求的点。
二分的本质：找到一个判断标准，使得查找区间能够一分为二。
通过图像我们可以发现，【A，B】 区间内的点都是严格大于 D 点的值的，C 点的值是严格小于 D 点的值的。但是当【C，D】区间只有一个元素的时候，C 点的值是可能等于 D 点的值的。
因此，初始化左右两个指针 left，right：
然后根据 mid 的落点，我们可以划分下一个查询的区间：
- 当 mid 在【A，B】区间的时候，也就是 mid 位置的值严格大于 D 点的值，下一次查询区间在【mid+1，right】上；
- 当
mid在【C，D】区间的时候，也就是 mid 位置的值严格小于等于 D 点的值，下次查询区间【left，mid】在上。
当区间长度变成 1 的时候，就是我们要找的结果。
C++算法代码：(以nums[ n - 1 ]为参照物)
class Solution { public: int findMin(vector<int>& nums) { //选择nums[n - 1]作为参照物 int left = 0; int right = nums.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] > nums[nums.size() - 1]) { left = mid + 1; } else { right = mid; } } return nums[left]; } };C++算法代码：(以nums[ 0 ]为参照物)
class Solution { public: int findMin(vector<int>& nums) { //选择nums[0]作为参照物 int left = 0; int right = nums.size() - 1; while(left < right) { int mid = left + (right - left + 1) / 2; if(nums[mid] >= nums[0]) { left = mid; } else { right = mid - 1; } }//循环结束left与right相遇的位置是数组最大值， //left+1位置则是最小值(数组不是一直递增的情况) if(left == nums.size() - 1)//特殊情况：旋转到数组一直递增 { return nums[0]; } return nums[left + 1]; } };算法总结及流程解析：
24.0~n-1中缺失的数字
题目链接：
LCR 173. 点名 - 力扣（LeetCode）
题目描述：
题目示例：
解法（二分查找）：
算法思路：
关于这道题中，时间复杂度为 O(N) 的解法有很多种，而且也都比较好想到，这里就不再赘述。本题我们主要介绍的是一个时间复杂度为 O(logN) 的最优解法二分法：
在这个升序的数组中，我们发现：
- 在第一个缺失位置的左边，数组内元素都是与数组下标相等的；
- 在第一个缺失位置的右边，数组内的元素都是与数组下标不相等的。
因此，我们可以利用这个【二段性】，来使用【二分查找】算法。
C++算法代码：
class Solution { public: int takeAttendance(vector<int>& records) { int left = 0; int right = records.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(mid >= records[mid]) { left = mid + 1; } else { right = mid; } } if(left == records[left]) { return records[left] + 1; } return records[left] - 1; } };算法总结及流程解析：
结束语
到此，23.寻找旋转排序数组中的最小值，24.0~n-1中缺失的数字 这两道算法题就讲解完了。旋转排序数组最小值：利用区间二段性，比较中点与右端点值，收缩查找范围至单个元素。缺失数字查找：根据元素值与下标关系二分，定位首个不匹配位置。希望大家能有所收获！
