【优选算法必刷100题】第023~24题（二分查找算法）：寻找/搜索旋转排序数组中的最小值、点名（缺失的数字）
【优选算法必刷100题】第023~24题（二分查找算法）：寻找/搜索旋转排序数组中的最小值、点名（缺失的数字）
艾莉丝努力练剑
发布于 2025-11-18 13:30:15
发布于 2025-11-18 13:30:15
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题（二分查找算法）：山脉数组的峰顶索引、寻找峰值
结语：都看到这里啦！请大佬不要忘记给博主来个“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡 ૮₍ ˶ ˊ ᴥ ˋ˶₎ა
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-10-21，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
