力扣81、搜索旋转排序数组Ⅱ

1、直接循环（4ms,90%;13.5MB,85%）

时间复杂度：O（n）：循环次数

空间复杂度：O（1）

 1  bool search(vector<int>& nums, int target) {
 2         if(nums.empty())
 3         return false;
 4         int n=0;
 5         while(n<nums.size()){
 6             if(target==nums[n])
 7             return true;
 8             n++;
 9         }
10         return false;
11     }

2、二分法（4ms,90%;13.4MB,98%）

时间复杂度：O（n）:当所有的数组元素都相等但和target不相等时需要访问所有的位置

空间复杂度：O（1）

bool search(vector<int>& nums, int target) {
       if(nums.empty())
       return false;
       if(nums.size()==1)
       return nums[0]==target? true:false;
       int left=0,right=nums.size()-1;
       int mid=0;
       while(left<=right){
           mid=(left+right)/2;
           if(nums[mid]==target)
           return true;
           //注意不要写成left==mid&&right==mid
           //如果三个下标对应的值都相等，无法判断左边还是右边有序
           //此时应该收缩范围，只保留中间的下标
           if(nums[left]==nums[mid]&&nums[right]==nums[mid]){
               left++;
               right--;
           }
           else if(nums[left]<=nums[mid]){
               if(target>=nums[left]&&target<nums[mid])
               right=mid-1;
               else
               left=mid+1;
           }
           else{
               if(target>nums[mid]&&target<=nums[right])
               left=mid+1;
               else
               right=mid-1;
           }
       }
       return false;
    }