跟进“搜索旋转排序数组”，假如有重复元素又将如何？

是否会影响运行时间复杂度？

如何影响？

为何会影响？

写出一个函数判断给定的目标值是否出现在数组中。

 

样例

给出[3,4,4,5,7,0,1,2]和target=4，返回 true

 

发现lintcode有一点不好就是这种O(n)的解法也能给过

1 bool search(vector
      
        &A, int target) { 2         // write your code here 3         vector
       
        ::iterator it=A.begin(); 4         while(it!=A.end()){ 5             if(target==*it){ 6                 return true; 7             } 8             it++; 9         }10         return false;11     }
       
      

应该给个超时什么的

下面来个正经的吧

1 bool search(vector
      
        &A, int target) { 2         int left=0,right=A.size()-1; 3         int mid; 4         while(left<=right){ 5             mid=(right+left)/2; 6             if(target==A[mid]){ 7                 return true; 8             } 9             if(A[mid]>A[left]){
     //left->mid之间有序10                 if(A[left] <= target && target < A[mid]) {11                     right = mid - 1;12                 }13                 else{14                     left = mid + 1;15                 }16             }17             else if(A[mid]
       
        right之间有序18                 if(A[mid] < target && target <= A[right])  {19                     left = mid + 1;20                 }21                 else  {22                     right = mid - 1;23                 }24             }25             else{
     //mid->right之间相同26                 left++;27             }28         }29         return false;30     }
       
      

在原先代码上略加修改，除了将返回类型改成对应的bool值之外，还要注意A[mid]==A[left]的情况，这也是这一题与上一题的主要区别

如果相同，说明后半全是相同元素，那么接着顺着找就行了