Problem: 33. 搜索旋转排序数组

思路

题目要求时间复杂度为$O(logN)O(logN)$，并且本题是一个升序数组经过部分旋转后的数组，所以我们可以使用二分法进行查找；

解题方法

1.解决方法：二分法查找，时间复杂度：$O(logN)O(logN)$,空间复杂度为 $O(1)O(1)$；

Code

class Solution {
public:
    int search(vector<int>& nums, int target) {
       int n=nums.size();
       if(!n) return -1;
       if(n==1) return nums[0]==target?0:-1;//判断特殊情况
       int l=0,r=n-1;
       while(l<=r)
       {
           int mid=(l+r)>>1;
           if(nums[mid]==target) return mid;//每次循环前判断是否符合要求，符合输出位置
           if(nums[mid]>=nums[0])//判断属于哪个部分
           {
               if(target>=nums[0]&&target<nums[mid])//在部分中使用二分法查找
                {
                    r=mid-1;
                }
                else
                {
                    l=mid+1;
                }
           }
           else
           {
                if(target>nums[mid]&&target<=nums[n-1])
                {
                    l=mid+1;
                }
                else{
                    r=mid-1;
                }
           }
       }
        return -1;//失败返回-1；
    }
};