public static int shiftedBinarySearch(int[] array, int target) {
    return shiftedSearch(array, 0, array.length - 1, target);
}

public static int binarySearch(int[] array, int startIdx, int endIdx, int target) {
        int midIdx = (startIdx + endIdx) / 2;

        if (startIdx > endIdx || endIdx >= array.length) {
            return -1;
        }

        if (startIdx == endIdx) {
            if (array[midIdx] == target) {
                return midIdx;
            } else {
                return -1;
            }
        }

        int result = -1;
        if (target <= array[midIdx]) {
            result = binarySearch(array, startIdx, midIdx, target);
        } else {
            result = binarySearch(array, midIdx + 1, endIdx, target);
        }

        return result;
    }

    public static int shiftedSearch(int[] array, int startIdx, int endIdx, int target) {

        if (startIdx > endIdx || endIdx >= array.length) {
            return -1;
        }

        if (array[startIdx] == target) {
            return startIdx;
        }

        if (array[endIdx] == target) {
            return endIdx;
        }

        int result = -1;
        int midIdx = (startIdx + endIdx) / 2;


        if (array[startIdx] > array[midIdx]) {
            result = shiftedSearch(array, startIdx, midIdx, target);
            if (result != -1) {
                return result;
            }
        }

        if (array[midIdx + 1] < array[endIdx]) {
            result = binarySearch(array, midIdx + 1, endIdx, target);
            if (result != -1) {
                return result;
            }
        }


        if (array[startIdx] < array[midIdx]) {
            result = binarySearch(array, startIdx, midIdx, target);
            if (result != -1) {
                return result;
            }
        }


        if (array[endIdx] < array[midIdx + 1]) {
            result = shiftedSearch(array, midIdx + 1, endIdx, target);
            if (result != -1) {
                return result;
            }
        }
        return result;
    }