二分查找实战：旋转数组最小值与缺失数字问题
1. 寻找旋转排序数组中的最小值
题目描述
已知一个升序排列的数组经过若干次旋转后，例如 [3,4,5,1,2]，请找出其中的最小元素。假设数组中不存在重复元素。
解题思路 这道题的核心在于利用旋转数组的'二段性'。虽然整体不是有序的，但在旋转点两侧，大小关系是确定的。
想象一下，如果我们把数组首尾相连看成一个环，最小值就是那个'折点'。在二分查找中，我们需要找到一个判断标准，让搜索区间能不断缩小。通常有两种策略：
- 以右端点为基准：比较中间值
mid和右端点nums[right]。如果mid大于右端点，说明最小值在右侧（因为左半部分整体比右半部分大）；否则最小值在左侧或就是mid。 - 以左端点为基准：比较中间值
mid和左端点nums[left]。逻辑类似，但需要注意处理数组未发生旋转的特殊情况。
当左右指针相遇时，即找到了目标位置。
代码实现（以右端点为参照） 这种方式逻辑相对直观，不需要额外判断是否旋转。
class Solution {
public:
int findMin(vector<int>& nums) {
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];
}
};
代码实现（以左端点为参照）
这种写法需要多一步特殊判断，因为如果数组本身有序，left 可能会指向最大值而非最小值。
class Solution {
public:
int findMin(vector<int>& nums) {
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 相遇的位置是数组最大值
if(left == nums.size() - 1) {
return nums[0];
}
return nums[left + 1];
}
};
2. 0~n-1 中缺失的数字
题目描述 一个长度为 n-1 的递增排序数组中的所有数字都在 0~n-1 范围内且无重复。找出其中缺失的那个数字。
解题思路 暴力解法遍历一遍即可，但既然数组有序，我们可以用二分查找将复杂度降为 O(logN)。
观察发现，如果没有缺失数字，数组下标 i 对应的值应该是 i。一旦某个位置的值 nums[i] != i，说明缺失的数字就在该位置或其左侧。这就是典型的二段性：
- 缺失位置左侧：
nums[i] == i - 缺失位置右侧：
nums[i] != i
我们只需要找到第一个满足 nums[i] != i 的位置，或者确定所有位置都匹配（此时缺失的是最后一个）。
代码实现
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;
}
};
这两道题展示了二分查找在不同约束条件下的变形应用。关键在于识别出问题的'单调性'或'二段性'，从而定义出正确的 mid 移动规则。在实际编码中，务必注意边界条件的收敛，避免死循环。
