北京seo网站推广费用汕头企业网站

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

解法：O(logn)->很可能就是二分查找

思路：再看看题目要求，可以画出旋转之后数组中元素的大小关系：

首先，数组是具有二段性的(适配二分查找)，因为原来的有序数组旋转元素挪到前面后，一定比后面的元素都要大，所以由此可以画出上图。

细节

1.以D为参照 ，判断mid落在[A,B],还是[C,D]区间内，最后如果求出[C,D]区间的左端点，也就是C，就知道了最终结果的下标。

2.以A为参照，那么最后一次旋转的元素变成数组首元素，也就是[A,B]最小的元素，但比[C,D]区间的值都要大，所以也是一种思路。[A,B]区间的值 >A,[C,D]区间的值 <A，其实还是求[C,D]区间的左端点。

3.以A为参照点时，考虑边界情况：旋转后 和 原数组 相同，那么数组首元素 > 尾元素。因为A为参照点时，是以首元素为参照，如果命中 nums[mid] >= sub 条件，则会越过最小元素。

上述两种参照点都可以解决问题，代码也都会给在下方，但注意：

根据在做题中学习（49）：排序数组中查找元素的第一个和最后一个位置-CSDN博客

中有更详细的求左区间的讲解和细节问题。

1.以A为参照

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

2.以D为参照

class Solution 
{
public:int findMin(vector<int>& nums) {int left = 0,right = nums.size()-1;int back = right;while(left < right){//求区间左端点int mid = left + (right - left) /2;if(nums[mid] > nums[back])left = mid + 1;else if(nums[mid] <= nums[back])right = mid;}//走到这里，left == rightreturn nums[left];}
};