【算法拾光】二分查找｜搜索旋转排序数组 + 寻找旋转排序数组中的最小值

题目 1：搜索旋转排序数组

链接：33. 搜索旋转排序数组 – 力扣（LeetCode）

题目分析

原始数组是升序数组，在某个下标位置进行旋转，数组被拆成两段升序子数组（例如 [4,5,6,7,0,1,2]）。 要求：给一个目标值 target，如果 target 在数组中返回下标，不存在返回 -1；数组无重复元素，时间复杂度要求 \\(O(logn)\\)，提示我们必须使用二分查找，不能直接遍历。 难点：数组不再全局有序，直接二分无法判断目标在哪一侧，需要先判断 mid 落在左半有序区还是右半有序区。

算法原理

旋转数组一定有一半区间是有序的：

代码编写

int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() – 1;
while(left <= right) {
int mid = left + (right – left) / 2;
if(nums[mid] == target) return mid;
// 左半段有序
if(nums[left] <= nums[mid]) {
if(target >= nums[left] && target < nums[mid]) {
right = mid – 1;
} else {
left = mid + 1;
}
} else {
// 右半段有序
if(target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid – 1;
}
}
}
return -1;
}

题目 2：寻找旋转排序数组中的最小值

链接：153. 寻找旋转排序数组中的最小值 – 力扣（LeetCode）

题目分析

同样是无重复升序数组旋转后的数组，例如 [3,4,5,1,2]，我们要找到数组里面最小元素。 最小值就是旋转点，旋转点的特点：最小值比它右边元素小，同时比左边元素小。 全局有序时（旋转 0 次）最小值就是第一个元素。要求 \\(O(logn)\\)，二分。

算法原理

核心判断：比较 nums[mid] 和 nums[right]

注意：这里不能写 right = mid – 1，因为 mid 本身有可能就是最小值 循环结束条件 left < right，最后 left == right，就是最小值下标。

代码编写

int findMin(vector<int>& nums) {
int left = 0, right = nums.size() – 1;
while(left < right) {
int mid = left + (right – left) / 2;
if(nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}

本篇总结

本篇两道题是二分查找的高频变种：旋转有序数组二分，不再依赖全局有序，利用「旋转数组必有一半有序」这个性质二分。