[LeetCode] Search in Rotated Sorted Array

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e.,0 1 2 4 5 6 7might become4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

解题思路：

题意为在旋转数组中找出目标数，与找最小数?type=article&article_id=111是兄弟题目。类似于二分查找，分析一下便可。

数组元素：XX XX… XX XX… XX

数组下标：start middle end

如上所示，

1、若middle等于目标值，，返回middle，若start等于目标值，则返回start，若end等于目标值，则返回end。

2、若middle大于目标值，并且start小于目标值，表示start到middle是顺序部分，且目标值肯定在start到middle部分（若存在的话），因此将end赋值为middle-1

3、若middle小于目标值，并且end大于目标值，表示middle到end是顺序部分，且目标值肯定在middle到end部分（若存在的话），因此将start赋值为middle+1

4、若middle大于目标值，并且start大于目标值，这要分情况讨论。若start到middle不是顺序部分，表明target在start到middle之间（若存在的话），否则在middle到end之间

5、若middle小于目标值，且end小于目标值，分情况讨论，若middle到end不是顺序部分，则target在middle到end之间（若存在的话），否则在start到middle之间。

下面是代码：

class Solution {public:int search(vector<int>& nums, int target) {int start=0;int end=nums.size()-1;int middle;while(start<=end){middle=(start+end)/2;if(nums[middle]==target){return middle;}else if(nums[start]==target){return start;}else if(nums[end]==target){return end;}else{if(nums[middle]>target&&nums[start]<target){end=middle-1;}else if(nums[middle]<target&&nums[end]>target){start=middle+1;}else if(nums[middle]>target&&nums[start]>target){if(nums[middle]>nums[start]){start=middle+1;}else{end=middle-1;}}else if(nums[middle]<target&&nums[end]<target){if(nums[middle]<nums[end]){end=middle-1;}else{start=middle+1;}}}}return -1;}};

游手好闲会使人心智生锈