leetcode 33. Search in Rotated Sorted Array

题目描述

可以发现的是，将数组从中间分开成左右两部分的时候，一定至少有一部分的数组是有序的。左部分[left,mid-1]，右部分[mid+1,right]。

第一种情况：左右两部分都是有序的，说明nums[mid]就是整个数组的最大值。此时只需要判断target在哪个部分，然后去那个部分做正常的二分查找即可。

第二种情况，左右两部分只有一部分是有序的。此时看target是否在有序的那部分。如果是，那就去有序的那部分做正常的二分查找。如果否，说明target在无序的部分，并且问题规模缩小一半，重复前面的逻辑即可。

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() -1;int mid = 0;while(left<=right){mid = left + ((right-left)>>1);if(nums[mid] == target)return mid;if(left <= mid-1 && nums[left] <= nums[mid-1])//左半部分有序{if(nums[left]<=target&&target<=nums[mid-1])//target在左半部分之中right = mid-1;elseleft = mid +1;}else//右半部分有序{if(mid+1<=right && nums[mid+1]<=target&&target<=nums[right])//target在右边部分之中left = mid+1;elseright = mid -1;}}return -1; }
};