public int search(int[] A, int target) {
        if (A == null || A.length == 0)
            return -1;
        int leftIndex = 0;
        int rightIndex = A.length - 1;
        
        int middle;
        
        while (leftIndex <= rightIndex) {
            middle = leftIndex + (rightIndex - leftIndex)/2;
            if (A[middle] == target)
                return middle;

            // the left part of array are sorted
            if (A[leftIndex] < A[middle]) {
                if (target >= A[leftIndex] && target < A[middle]) {
                    // the target failed into left side
                    rightIndex = middle - 1;
                } else {
                    
                    leftIndex = middle + 1;
                }
            }
            // the right part of array are sorted
            else {
                if (target > A [middle] && target <= A[rightIndex]) {
                    leftIndex = middle + 1;
                } else {
                    rightIndex = middle - 1;
                }
            }
            
        }
        
        return -1;
    }