leetcode 153 寻找旋转排序数组中的最小值

一、题目描述

二、解题思路

nums[right]可以把向量分为两段，如图所示。具有“二段性”，可以使用二分法来解决这个问题。最小值为nums[mid]<nums[right]的左边界，情况二和情况一均可以用此代码解决。

请思考：能否用nums[left]作为比较基准来解决此问题？

不能，如果为情况二，则查找到的数不为最小值。

三、代码实现

时间复杂度：T(n)=O(log2)

空间复杂度：S(n)=O(1)

class Solution {public: int findMin(vector& 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; } return nums[left]; }};