[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 条评论

    发表评论

    电子邮件地址不会被公开。 必填项已用 * 标注