Follow up for "":

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.

1 class Solution { 2 public: 3     bool search(int A[], int n, int target) { 4         int start = 0, end = n - 1; 5         while (start <= end) { 6             int mid = (start + end) / 2; 7             if (A[mid] == target) return true; 8             if (A[start] < A[mid]) { 9                 if (A[start] <= target && A[mid] > target) {10                     end = mid - 1;11                 } else {12                     start = mid + 1;13                 }14             } else if (A[start] > A[mid]) {15                 if (A[mid] < target && A[end] >= target) {16                     start = mid + 1;17                 } else {18                     end = mid - 1;19                 }20             } else {21                 ++start;22             }23         }24         return false;25     }26 };

整体上与上题（Search in Rotated Sorted Array）差别不大，额外的是：若数组中存在重复元素，那么区间首尾元素相等时无法确定区间内是否发生过rotate，此时跳过首元素继续找。