【优选算法必刷100题】第023~24题（二分查找算法）：寻找/搜索旋转排序数组中的最小值、点名（缺失的数字）
🔥艾莉丝努力练剑：个人主页
❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬艾莉丝的简介：
🎬艾莉丝的算法专栏简介：
目录
023 寻找/搜索旋转排序数组中的最小值
力扣链接：153. 寻找旋转排序数组中的最小值
力扣题解链接：二分查找模版解决【寻找旋转排序数组中的最小值】
题目描述：
1.1 解法一：暴力查找
关于暴力查找，只需遍历一遍数组，这里不再赘述。
1.2 解法二：二分查找
1.2.1 算法思路
题目中的数组规则如下图所示——
这个C点就是我们要求的点。
二分的本质：找到一个判断标准，使得查找区间能够一分为二——二段性。
通过图像我们可以发现，[A , B]区间内的点都是严格大于点的值的，C点的值是严格小于D点的值的。但是当[C , D]区间只有一个元素的时候，C点的值是可能等于D点的值的。
因此，初始化左右两个指针left，right。
然后根据mid的落点，我们可以这样划分下一次查询的区间——
（1）当mid在[A , B]区间的时候，也就是mid位置的值严格大于D点的值，下一次查询区间在[mid + 1 , right]上；
（2）当mid在[C , D]区间的时候，也就是mid位置的值严格小于等于D点的值，下次查询区间在[left , mid]上。
当区间长度变成1的时候，就是我们要找的结果。
1.2.2 算法实现
代码演示如下——
// D点 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[left]; // 返回数组中的最小元素 } };时间复杂度：O(logn)，空间复杂度：O(1)。
1.2.3 尝试：选择A点呢？
A点也可以有二段性，我们可以尝试一下——
int y = nums[left]; // 选择第一个元素作为参考点 while(left < right) { int mid = left + (right - left + 1) / 2; if(nums[mid] >= y) right = mid - 1; // 还在左半部分，往右找 else left = mid; // 已经在右半部分，往左找 }问题：当数组没有旋转时（如[1 , 2 , 3 , 4 , 5]），所有元素都 >= nums[0]，会导致一直执行 right = mid - 1，最终返回错误的结果。
1.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
024 点名（缺失的数字）
力扣链接：LCR 173. 点名
力扣题解链接：二分查找模版解决【点名】
题目描述：
2.1 解法一：暴力遍历找结果
代码演示如下——
class Solution { public: int takeAttendance(vector<int>& records) { int n = records.size(); for (int i = 0; i < n; i++) { if (records[i] != i) { return i; } } return n; // 如果前面都连续，缺失的就是最后一个 } };时间复杂度：O(n)，空间复杂度：O(1)。
2.2 解法二：用哈希表解决
代码演示如下——
class Solution { public: int takeAttendance(vector<int>& records) { unordered_set<int> recordSet(records.begin(), records.end()); int n = records.size(); for (int i = 0; i <= n; i++) { if (recordSet.find(i) == recordSet.end()) { return i; } } return -1; } };时间复杂度：O(n)，空间复杂度：O(n)。
2.3 解法三：位运算
代码演示如下——
class Solution { public: int takeAttendance(vector<int>& records) { int result = 0; int n = records.size(); // 将 0~n 的所有数与数组中的数进行异或 for (int i = 0; i <= n; i++) { result ^= i; } for (int num : records) { result ^= num; } return result; } };时间复杂度：O(n)，空间复杂度：O(1)。
2.4 解法四：用（数学）高斯求和公式解决
代码演示如下——
class Solution { public: int takeAttendance(vector<int>& records) { int n = records.size(); // 计算 0~n 的完整和 int totalSum = n * (n + 1) / 2; // 计算实际数组的和 int actualSum = 0; for (int num : records) { actualSum += num; } // 缺失的数 = 完整和 - 实际和 return totalSum - actualSum; } };时间复杂度：O(n)，空间复杂度：O(1)。
2.5 解法五：二分查找（最优解）
2.5.1 算法思路
关于这道题中，时间复杂度为O(N) 的解法有很多种，而且也是比较好想的，就是上面我们已经展示过的四种方法，已经介绍过了，这里就不再赘述。
在这个升序的数组中，我们发现——
（1）在第一个缺失位置的左边，数组内的元素都是与数组的下标相等的；
（2）在第一个缺失位置的右边，数组内的元素与数组下标是不相等的。
因此，我们可以利用这个【二段性】，来使用【二分查找】算法。
2.5.2 算法实现
代码演示如下——
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; } };时间复杂度：O(logn)，空间复杂度：O(1)。
2.6 五种方法总结
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 哈希表 | O(n) | O(n) | 通用解法 |
| 直接遍历 | O(n) | O(1) | 简单直观 |
| 位运算 | O(n) | O(1) | 无溢出风险 |
| 高斯求和 | O(n) | O(1) | 数学思维 |
| 二分查找 | O(log n) | O(1) | 最优解 |
推荐使用二分查找，因为它的时间复杂度最优，且能充分利用数组有序的特性。
2.7 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己能够推导很重要！
结尾
往期回顾：
【优选算法必刷100题】第021~22题（二分查找算法）：山脉数组的峰顶索引、寻找峰值
结语：都看到这里啦！请大佬不要忘记给博主来个“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡
૮₍ ˶ ˊ ᴥ ˋ˶₎ა
