解题思路
本道题目是采用二分搜索来实现的,二分搜索时,一定要找到一个判别条件;
使得最终要查找的结果可以确定在左半边,或者是右半边;
既然是旋转之前数组是递增的,那么nums[0]就可以成为一个二分判断条件;
对于本道题首先要解决两种特殊情况;
一是,对于头尾相同的数组,当最后面的值和nums[0] 相等时这种二分特性就被打破了,所以应该先去尾;
还有一种旋转后还是单调递增的就直接返回第一项就行了;
具体代码如下;
代码
class Solution {
public:
int minArray(vector<int>& nums) {
//既然是旋转之前数组是递增的,那么nums[0]就可以成为一个二分判断条件
//当最后面的值和nums[0] 相等时这种二分特性就被打破了,所以应该先去尾
int left = 0,right = nums.size() - 1;
while(right != left && nums[right] == nums[0]) right--;
if(nums[right] >= nums[0] ) return nums[0];
while(left < right){
int mid = left + right >>1;
if(nums[mid] < nums[0]) right = mid;
else left = mid + 1;
}
return nums[left];
}
};