[LeetCode]Search in Rotated Sorted Array II

[cpp] 
class Solution { 
//classified discussion  
//1. Based on the property of rotated array, there may or may not have one sorted sequence   
//when one sequence is divided into two parts    
//2. make decision under all these cases  
public: 
    bool search(int A[], int n, int target) { 
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        return BinarySearch(A, n, target); 
    } 
 
 
    bool BinarySearch( int* A, int n, int target )  
    { 
        //throw std::exception("The method or operation is not implemented.");  
        int l = 0; 
        int r = n-1; 
        while (l <= r) 
        { 
            int m = l+(r-l)/2; 
            if(A[m] == target) return true; 
            if (A[l] < A[m])//left subsequence sorted  
            { 
                if(A[l] <= target && target < A[m]) 
                    r = m-1; 
                else l = m+1; 
            } 
            else if (A[m] < A[r]) 
            { 
                if(A[m] < target && target <= A[r]) 
                    l = m+1; 
                else r = m-1; 
            } 
            else if (A[l] == A[m])//A[m] is not the target, so remove en element equal to A[m] is safe  
                l++; 
            else if(A[m] == A[r])//ditto  
                r--; 
        } 
        return false; 
    } 
}; 

class Solution {
//classified discussion
//1. Based on the property of rotated array, there may or may not have one sorted sequence
//when one sequence is divided into two parts 
//2. make decision under all these cases
public:
 bool search(int A[], int n, int target) {
  // Start typing your C/C++ solution below
  // DO NOT write int main() function
  return BinarySearch(A, n, target);
 }

 bool BinarySearch( int* A, int n, int target )
 {
  //throw std::exception("The method or operation is not implemented.");
  int l = 0;
  int r = n-1;
  while (l <= r)
  {
   int m = l+(r-l)/2;
   if(A[m] == target) return true;
   if (A[l] < A[m])//left subsequence sorted
   {
    if(A[l] <= target && target < A[m])
     r = m-1;
    else l = m+1;
   }
   else if (A[m] < A[r])
   {
    if(A[m] < target && target <= A[r])
     l = m+1;
    else r = m-1;
   }
   else if (A[l] == A[m])//A[m] is not the target, so remove en element equal to A[m] is safe
    l++;
   else if(A[m] == A[r])//ditto
    r--;
  }
  return false;
 }
};