编程开发习题: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 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.

在旋转有序数组中，查找元素，直接遍历O(n)的复杂度显然不符合题目要求。考虑到旋转有序数组中，至少有一半的数组是有序的，所以还是可以采用二分法，只是稍微有些变动。取数组的中点nums[n/2]，如果nums[n/2]nums[n-1]，说明数组左边是有序的。因此

根据数组的有序部分可以判断查找的元素在数组的左边还是右边，然后就可以继续进行二分，时间复杂度为O(logn)。

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