《算法题讲解指南：优选算法-二分查找》--23.寻找旋转排序数组中的最小值，24.0~n-1中缺失的数字

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》

《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

目录

23.寻找旋转排序数组中的最小值

题目链接：

题目描述：

题目示例：

解法（二分查找）：

算法思路：

C++算法代码：(以nums[ n - 1 ]为参照物)

C++算法代码：(以nums[ 0 ]为参照物)

算法总结及流程解析：

24.0~n-1中缺失的数字

题目链接：

题目描述：

题目示例：

解法（二分查找）：

算法思路：

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中缺失的数字 这两道算法题就讲解完了。旋转排序数组最小值：利用区间二段性，比较中点与右端点值，收缩查找范围至单个元素。缺失数字查找：根据元素值与下标关系二分，定位首个不匹配位置。希望大家能有所收获！