public boolean searchAux(int[] A, int target, int low, int high) {

        if (low > high) {
            return false;
        }

        //divide into two parts
        int mid = (low + high) / 2;
        //find the target
        if (A[mid] == target) {
            return true;
        }

        //search in each part, remove the equal situation to avoid the duplicate
        if (A[low] < A[mid]) {
            if (target >= A[low] && target < A[mid]) {
                return searchAux(A, target, low, mid - 1);
            } else {
                return searchAux(A, target, mid + 1, high);
            }
        } else if (A[mid] < A[low]) {
            if (target > A[mid] && target <= A[high]) {
                return searchAux(A, target, mid + 1, high);
            } else {
                return searchAux(A, target, low, mid - 1);
            }
        } //in order to avoid the duplicate
        else {
            low++;
            return searchAux(A, target, low, high);
        }
    }