[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 7
might become 4 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.
解题思路:
题意为在旋转数组中找出目标数,与找最小数http://www.kangry.net/blog/?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; } };
0 条评论