33. Search in Rotated Sorted Array 在旋转有序数组中搜索

Suppose an array sorted in ascending order 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.

Difficulty: Medium

这道题让我们求一个旋转有序数组中是否存在一个给定的值,存在返回下标,不存在返回-1.如体重的例子0 1 2 4 5 6 7,我们不知道从哪开始旋转的,他的选择情况有7种

0  1  2   4  5  6  7

7  0  1   2  4  5  6

6  7  0   1  2  4  5

5  6  7   0  1  2  4

4  5  6  7  0  1  2

2  4  5  6  7  0  1

1  2  4  5  6  7  0

这里采用二分搜索法.从上面可以看出取出中位数后,他的左半段或右半段总有一个是有序的.我们可以比较nums[mid]和nums[right]来决定哪部分是有序的.找到有序的一部分后我们只需要比较有序部分的首尾两个数就可以知道target是否在有序的这部分了.

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n==0) return -1;
        int left = 0,right = n-1;
        while (left <= right)
        {
            int mid = (left+right)/2;
            if (nums[mid]==target) return mid;
            else if (nums[mid]<nums[right])
            {
                if (nums[mid]<target&&nums[right]>=target)
                    left = mid+1;
                else 
                    right = mid-1;
            }
            else
            {
                if (nums[left]<=target&&nums[mid]>target)
                    right=mid-1;
                else
                    left = mid+1;
            }
        }
        return -1;
    }
};
 
comments powered by Disqus