23. 寻找旋转排序数组中的最小值
题目链接
题目描述
题目示例
解法（二分查找）
算法思路
题目中的数组规则如下图所示：
其中 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 中缺失的数字
题目链接
题目描述
题目示例
解法（二分查找）
算法思路
关于这道题中，时间复杂度为 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;
}
};
算法总结及流程解析
