Follow up for "Search in Rotated Sorted Array":

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

 

分析

如果允许重复元素，则Search in Rotated Sorted Array题中如果 A[m]>=A[l], 那么 [l,m] 为递增序列的假设就不能成立了，比

如 [1,2，3,1,1,1]。

如果 A[m]>=A[l] 不能确定递增，那就把它拆分成两个条件：

• 若 A[m]>A[l]，则区间 [l,m] 一定递增

• 若 A[m]==A[l] 确定不了，那就 l++，往下看一步即可。

Search in Rotated Sorted Array 的code：

 

1 class Solution { 2 public: 3     bool search(int A[], int n, int target) { 4         int low = 0; 5         int high = n-1; 6         int mid ; 7  8          9         while(low<=high)10         {11             mid= (low + high)/2;12             13             if(A[mid]==target)14             {15                 return true;16             }17                     18             if(A[low]<=A[mid]) // the pivot is in the bottom half19             {20                 if(A[low]<=target && target < A[mid]) //target in the first half21                     high = mid-1;22                 else23                     low = mid+1;//target in the bottom half24             }25             else // the pivot is in the first half26             {27                 if(A[mid] < target && target <= A[high])// the pivot is in the first half28                     low = mid+1;29                 else //target in the first half30                     high = mid-1;31             }32             33         }34         return false;35         36     }37 };

 

 

将if (A[low] <= A[mid]) 拆成if (A[low] < A[mid]) 和 if (A[low] == A[mid]) 两个分支，code如下：

1 class Solution { 2 public: 3     bool search(int A[], int n, int target) { 4         int low = 0; 5         int high = n-1; 6         int mid ; 7  8          9         while(low<=high)10         {11             mid= (low + high)/2;12             13             if(A[mid]==target)14             {15                 return true;16             }17                     18             if(A[low]
     
       A[mid])26             {27                 if(A[mid] < target && target <= A[high])28                     low = mid+1;29                 else 30                     high = mid-1;31             }32             else 33                 low++;34             35         }36         return false;37         38     }39 };