[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., You are given a target value to search. If found in the array return its index,otherwise return ⑴. You may assume no duplicate exists in the array. 解题思路： 题意为在旋转数组中找出目标数，与找最小数http://www.kangry.net/blog/?type=article&article_id=111是兄弟题目。类似于2分查找，分析1下即可。 数组元素：XX XX... XX XX... XX 数组下标：start middle end 如上所示， 1、若middle等于目标值，返回middle，若start等于目标值，则返回start，若end等于目标值，则返回end。 2、若middle大于目标值，并且start小于目标值，表示start到middle是顺序部份，且目标值肯定在start到middle部份（若存在的话），因此将end赋值为middle⑴ 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()⑴;
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⑴;
}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⑴;
}
}else if(nums[middle]<target&&nums[end]<target){
if(nums[middle]<nums[end]){
end=middle⑴;
}else{
start=middle+1;
}
}
}
}
return ⑴;
}
}; （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |