【Leetcode每日一题】二分查找 - 寻找旋转排序数组中的最小值（难度⭐⭐）（22）

news/发布时间2024/9/20 8:03:10

1. 题目解析

Leetcode链接：153. 寻找旋转排序数组中的最小值

这个题目乍一看很长很复杂，又是旋转数组又是最小值的

但是仔细想想，结合题目给的示例，不难看出可以用二分的方法来解决

核心在于找到给定数组里面的最小值

2. 算法原理

题目规定的数组规则如下图所示：

我们的目标是找到一个特定的点C。

从给定的图像中，我们观察到在区间[A，B]内的所有点的值都严格大于D点的值，而C点的值则严格小于D点的值。但需要注意的是，当区间[C，D]只包含一个元素时，C点的值有可能等于D点的值。

因此，我们初始化两个指针，left和right，分别代表搜索区间的左右边界。接着，根据中间点mid的值与D点值的比较结果，我们可以确定下一次搜索的区间：

如果mid位于[A，B]区间内，即mid的值严格大于D点的值，那么下一次搜索区间将缩小为[mid + 1，right]。
如果mid位于[C，D]区间内，即mid的值小于或等于D点的值，那么下一次搜索区间将缩小为[left，mid]。

当搜索区间的长度缩减为1时，我们就找到了所需的点C。

3. 代码编写

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