public int search(int[] A, int target) {
        //find pivot
        int pivot = 0;
        for (int i = 1; i < A.length; i++) {
            if (A[i - 1] > A[i]) {
                pivot = i;
                break;
            }
        }

        int relativeStart = 0;
        int relativeEnd = A.length - 1;
        while (relativeStart <= relativeEnd) {
            int relativeMid = (relativeStart + relativeEnd) / 2;
            int mid = pivot + relativeMid >= A.length ? pivot + relativeMid - A.length : pivot + relativeMid;

            if (A[mid] == target) {
                return mid;
            } else if (A[mid] > target) {
                relativeEnd = relativeMid - 1;
            } else {
                relativeStart = relativeMid + 1;
            }


        }

        return -1;
    }