public int search(int[] A, int target) {
        //return searchin(A, 0, A.length - 1, target);
        int left = 0, right = A.length - 1, mid;

        while (left <= right) {
            mid = (left + right) / 2;
            if (A[mid] == target) return mid;
            if (left == right - 1) return A[right] == target ? right : -1;
            if (A[left] < A[mid]) {
                if (A[left] <= target && target < A[mid])
                    right = mid - 1;
                else left = mid + 1;
            }
            else {
                if (A[right] >= target && target >= A[mid])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return -1;
    }