LeetCode之Search in Rotated Sorted Array II

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 问题一不小心顺便搞定了。

class Solution {
public:
    bool search(int A[], int n, int target) {
        int start=0,end=n-1,mid;
        while(start<=end){
           mid=(start+end)>>1;
           if(A[mid]==target)  return true;
           
           if(A[mid]>A[start]){//left side is sorted
               if(A[start]<=target && A[mid]>target)
                    end=mid-1;
               else
                    start=mid+1;
           }else if(A[mid]<A[start]){//right side is sorted
               if(A[end]>=target && A[mid]<target)
                    start=mid+1; 
               else
                  end=mid-1; 
           }else
                start++;         //avoid end=mid=start
        }//while
        return false;
    }
};

LeetCode之Search in Rotated Sorted Array II,布布扣,bubuko.com

LeetCode之Search in Rotated Sorted Array II

原文：http://blog.csdn.net/smileteo/article/details/22663985