Follow up for "Remove Duplicates": What if duplicates are allowed at most twice? For example, Given sorted array A = [1,1,1,2,2,3], Your function should return length = 5, and A is now [1,1,2,2,3].

LeetCode-Remove Duplicates from Sorted Array II

C++:
class Solution {
public:
    bool search(int A[], int n, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int low=0;
        int high=n-1;
        int mid;
        while(low<=high){
            mid=low+(high-low)/2;
            if(A[mid]==target) return true;
            else if(A[mid]<target){
                if(A[mid]>A[low]) low=mid+1;
                else if(A[mid]<A[low]){
                    if(A[high]>target) low=mid+1;
                    else if(A[high]<target) high=mid-1;
                    else return true;
                }
                else low++;
            }else{
                if(A[mid]<A[high]) high=mid-1;
                else if(A[mid]>A[high]){
                    if(A[low]>target) low=mid+1;
                    else if(A[low]<target) high=mid-1;
                    else return true;
                }
                else high--;
            }
        }
        return false;
    }

};
Java:
public class Solution {
    public boolean search(int[] A, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int low=0;
        int high=A.length-1;
        int mid;
        while(low<=high){
            mid=low+(high-low)/2;
            if(A[mid]==target) return true;
            else if(A[mid]<target){
                if(A[mid]>A[low]) low=mid+1;
                else if(A[mid]<A[low]){
                    if(A[high]>target) low=mid+1;
                    else if(A[high]<target) high=mid-1;
                    else return true;
                }
                else low++;
            }else{
                if(A[mid]<A[high]) high=mid-1;
                else if(A[mid]>A[high]){
                    if(A[low]>target) low=mid+1;
                    else if(A[low]<target) high=mid-1;
                    else return true;
                }
                else high--;
            }
        }
        return false;
    }
}