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的判断标准去判断哪部分有序，设想一种情形1，1, 1，2，1,1,1，恰好左中右都是1,这时我们 ++左下标，--右下标，为什么这样我们不会将这个值跳过呢？ 就是说，凭什么我们说除却这两个位置，在两者之间就一定还存在这个值？当然能，因为我们进入的条件是左中右相等，所以我们可以把首尾的值都略过，进行下一次循环。
classSolution
{public: bool
search(intA[],
intn,
inttarget) { if(0==
n) returnfalse; intleft
= 0; intright
= n - 1; while(left
<= right) { intmidle
= (left + right) >> 1; if(A[midle]
== target) returntrue; if(A[left]
== A[midle] && A[midle] == A[right]) { ++left; --right; } elseif(A[left]
<= A[midle]) { if(A[left]
<= target && target < A[midle]) { right
= midle - 1; } else left
= midle + 1; } else{ if(A[midle]
< target && target <= A[right]) left
= midle + 1; else right
= midle - 1; } } returnfalse; }};