题目

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

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

The array may contain duplicates.

分析：

该题的拓展33.Search in Rotated Sorted Array：http://www.jianshu.com/p/9248237a76e2 ，直接使用该题思路即可，先将数组快速排序，然后二分法找到目标值是否存在。
C代码如下：

void sort(int *a, int left, int right)
{
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }
         
        a[i] = a[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/
         
        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }
         
        a[j] = a[i];
    }
     
    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                       /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

bool search(int* nums, int numsSize, int target) {
    sort(nums,0,numsSize-1);
    int p=0,q=numsSize-1;
    while(p<q)
    {
        if(nums[(p+q)/2]>target)q=(p+q)/2-1;
        else if(nums[(p+q)/2]<target)p=(p+q)/2+1;
        else return true;
    }
    if(p==q&&nums[p]==target)return true;
    else return false;
}

还有一个思路：数组分为递增的两段，第一段最小值大于第二段的最大值，因此可以直接使用二分法来判断目标值在哪一段中。
先判断中间点处于哪一段，然后针对目标值，选择合适的区间。不断逼近目标值。

bool search(int* nums, int numsSize, int target) {
    int p=0,q=numsSize-1;
    while(p<q)
    {
        //printf("%d %d\n",p,q);
        int mid=(p+q)/2;
        if(nums[mid]==target)return true;
        if(nums[mid]<nums[q])
        {
            if(nums[mid]<target&&nums[q]>=target)p=mid+1;
            else q=mid-1;
        }
        else if(nums[mid]>nums[q])
        {
            if(nums[mid]>target&&nums[p]<=target)q=mid-1;
            else p=mid+1;
        }
        else
            q--;
    }
    if(p==q&&nums[p]==target)return true;
    else return false;
}