- 1. 题目链接
- 2. 题目描述
- 3. 解题方法
- 4. 代码
1. 题目链接
153. 寻找旋转排序数组中的最小值
2. 题目描述
3. 解题方法
根据题目分析,可以明确一点,无论该数组如何旋转,都会有这样的一个性质,就是nums[0] > nums[n-1](除非旋转之后变回原数组)。
那么根据这一性质,数组就具有了二段性,就可以用二分法来解决问题。
4. 代码
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
// 二分查找,根据nums[mid]的情况判断最小值在哪半个区间
while(l < r)
{
int mid = (r - l) / 2 + l;
if(nums[mid] <= nums[nums.size() - 1])
{
// nums[mid]小于等于最后一个数,最小值在mid左半区间
r = mid;
}
else
{
// nums[mid]大于最后一个数,最小值在其右半区间
l = mid + 1;
}
}
return nums[r]; // 结果存储在r中
}
};
最后附上我的打卡记录,希望各位大佬可以监督我一下。