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.

思路：解题思路和差不多，但是出现了另一种情况有重复元素出现，头尾指针各向中间移一步。然后在进行判断。

class Solution {public:    bool search(int A[], int n, int target) {        if(A==NULL||n==0)            return -1;        int index1=0;        int index2=n-1;        int middle;        while(index1
     
      =A[index1])            {                if(target>=A[index1]&&target<=A[middle])                    index2=middle;                else                    index1=middle+1;            }            else            {                if(target<=A[index2]&&target>=A[middle])                    index1=middle;                else                    index2=middle-1;            }        }        if(index2>=0&&index2